Автоматное программирование. Часть 3. Диаграмма состояний и переходов. Продолжение

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

    Оглавление

    Диаграмма состояний != граф-схема.


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

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

    image

    Рисунок 1 а). Исходная граф-схема

    image

    Рисунок 1 б), в). Диаграммы состояний эквивалентных автоматов, реализующих алгоритм
    (а).


    На рис 1 (в) приведён пример некорректной записи диаграммы состояний и переходов. Некорректность в том, что переходы выделенные красным прямоугольником определяются не только входными событиями, но и дополнительно флагом с, который для этого состояния соответствует одноимённому флагу исходной граф-схемы рис. 1 (а), из-за чего уже нельзя отслеживать состояние процесса, рассматривая только входные символы, нужно каким-то образом учитывать логику изменения флага c. Проблема даже не в самом флаге с, а в том, что логика изменения этого флага не привязана к одному только состоянию s1. Если бы события связанные с изменением этого флага были бы связаны только с s1, такой проблемы не было бы. Выделенные красным цветом переходы зависят от того, каким путём попали в s1, что противоречит определению автомата, согласно которому реакция зависит только от входного символа и текущего состояния. Назовём это принцип автоматности, чтобы ссылаться на него дальше по тексту.

    Граф-схему ярко выраженной неавтоматной реализации алгоритма рис. 1 (а) не так просто записать в виде корректной диаграммы состояний, поскольку явно не определены состояния, и соответственно не определены переходы между ними. Для составления диаграммы рис. 1 (б) по алгоритму рис. 1 (а) потребовалось получить эквивалентный автомат. Методика получения эквивалентных автоматов для любой граф-схемы станет предметом рассмотрения в одной из следующих статей, сейчас ограничусь констатацией, что это принципиально можно сделать, потому что любое цифровое устройство, в том числе и любая «неавтоматная» программа, это цифровой автомат, который обладает состояниями в математическом смысле, несмотря на то, что эти состояния явно не описаны. Такие состояния подобны квантовым фотонам в квантовой электродинамике, их можно упрощённо описать: они везде и нигде конкретно, но они существуют и действуют.

    В этом примере, в силу случайности, каждая ветвь граф-схемы соответствует одному состоянию. Другими словами, каждый выходной символ получается только в одном состоянии. Однако, будь логика изменения флагов иной, оказалось бы, что один выходной символ получается в нескольких разных состояниях, или если сказать иначе — одна и та же ветвь граф-схемы соответствует нескольким разным состояниям. Это ещё более сложный с точки зрения понимаемости случай.

    Поскольку речь зашла о состояниях, возникает совершенно естественный вопрос: «с каким количеством состояний придётся иметь дело?». При автоматной реализации количество состояний мы задаём в известной мере произвольно, исходя из потребностей.

    В случае неавтоматного подхода, количество потенциальных состояний эквивалентного автомата составляет величину до:

    $$display$$2^\text{суммарная_разрядность_всех_переменных_определяющих_поведение, бит. }$$display$$


    То есть добавление даже одной переменной определяющей поведение, типа bool удвоит количество «структурных», условно назову их «схемотехнических возможных» состояний. Многие из этих состояний — недостижимые состояния. Все недостижимые состояния исключаются автоматически, специально подобранной логикой действий над переменными определяющими поведение и предполагается, что эти действия, налагаясь одно на другое, дадут требуемый результат. С точки зрения психологии, напомню, это динамический процесс как последовательность разнонаправленных действий дающих в итоге требуемый результат. Как было сказано ранее, очень сложная форма для понимания. Неплохой аналогией отличия между автоматным описанием (диаграмма состояний) и алгоритмическим описанием (граф схема) динамического процесса может быть исследование вместо графика функции графика её производной.

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

    Следует пояснить термин Переменная определяющая поведение. В случае неавтоматной реализации это фактически любая переменная, создающая ветвление алгоритма. В случае автоматной реализации это переменная Внутреннее состояние. В качестве переменной Внутреннее состояние может быть переменная типа перечисление, где перечислены все состояния(=просто int), или даже просто переменная типа bool если всего два состояния. Далее я продемонстрирую разные варианты программных реализаций автоматов.

    Как уже было сказано в начале статьи, граф-схема это не только форма записи автомата, но и форма записи обычного алгоритма. То, что операция условного перехода изображается стрелкой перехода, думаю, не вызывает удивления, но как изобразить цикл? Допустим наш автомат перебирает прямоугольную таблицу, то есть общее число комбинаций переменных вертикального и горизонтального циклов составит m * n. значит ли что у результирующего автомата будет столько же состояний, или иными словами как записать в автоматном стиле цикл?

    Рассмотрим цикл:

    for(i = 5; i--; ){}

    C точки зрения условия этого цикла значения счётчика 5,4,3,2,1 – одно и то же значение. Да, внутри тела цикла i это параметр, поведение программы отличается при разных значениях этого параметра, но с точки зрения режима работы цикла for, переменная-счётчик может принимать два значения 0 и не 0. Переменная i это так сказать псевдофлаговая переменная.
    Возвращаясь к автомату обхода таблицы, отмечу, что этот автомат имеет два состояния и две псевдофлаговые переменные:

    • счётчик горизонтального цикла, определяет состояние:
      {0} – Вертикальный цикл,
      {1,…,5,…} – Горизонтальный цикл,
    • счётчик вертикального цикла определяет условие окончания работы.

    image

    Рисунок 2. Запись вложенных циклов при помощи диаграммы состояний.

    Автомат Out_text из примера в «Введении» показанный на рис. 3 представляет интерес с точки зрения событий, вызывающих изменение состояния автомата.

    image

    Рисунок 3. «Автомат отображения текстовых блоков», диаграмма состояний.

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

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

    image

    Рисунок 4. Граф-схема, соответствующая автомату, описываемому рис. 1 (б)

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

    Артефакты автоматной схемотехники.


    Чтобы лучше понимать о чём идёт речь, введём две категории программных автоматов – символьные и функциональные. Символьные автоматы это автоматы, принимающие последовательность символов на входе, и выдающие последовательность символов на выходе. Это полный аналог классических абстрактных автоматов, автоматов которые собственно и рассматривает дискретная математика. Символьные автоматы используются для распознавания кодов, разбора регулярных выражений, лингвистического анализа, а так же для оптимизации функциональных автоматов, и алгоритмов в целом. Мы затронем способы их реализации далее в сегодняшней статье, и подробно обсудим в одной из следующих статей.

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

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

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

    image

    Рисунок 5. Общепринятый шаблон реализаций программных автоматов

    Это приводит к тому, что процесс проектирования становится громоздким, включающим в себя не нужные в большинстве случаев формальные шаги, предписываемые этим шаблоном.
    Но не превращение реально происходящих процессов в набор формализованных сигналов или использование некоторого «автоматного» API даёт преимущество автоматному программированию. Преимущество даёт запись динамического процесса в категориях диаграммы состояний, это делает программирование более предсказуемым. Грамотное разбиение автомата на операционный и управляющий автоматы, и как часть этого разбиения -правильный, разумный выбор операционного автомата, вот что делает решение эффективным, и в следующей статье будет это будет убедительно показано.

    Механическое копирование поведения разработчика схемотехнических автоматов, вот что я имел ввиду под словом артефакты, от которых автоматное программирование избавляется, покидая колыбель автоматной схемотехники, мы ведь имеем дело с программой. Программа чрезвычайно удобный и пластичный материал, и именно пластичность этого материала сделала его столь популярным. Программируя обычным способом, мы избавлены от рутины проектирования цифровых схем. Когда нам нужно выполнить действие, мы проверяем условие и выполняем его, и не требуется писать специальную функцию-триггер. О чём я? Можно написать так:


    if(IO_latch->Data_1_received && IO_latch->Permission)
    {
      State = 5;
    }
    

    а можно и так

    
    typedef bool paTrigger();
    typedef void paAction();
    
    struct tLink_Trigger_Action
    {
    
      paTrigger * Trigger;
      paAction * Action;
      int Next_state;
    
    };
    
    bool Trigger_X(){return(IO_latch->Data_1_received && IO_latch->Permission);};
    
    void Action_X(){State = 5;};
    
    
    tLink_Trigger_Transition Table[States_max][ Triggers_max] = {
    /*State_0*/{},
    /*State_1*/{ …,{ Trigger_X, Action_X }, … },
    /*State_2*/{},
    /*State_3*/{},
    /*State_4*/{}};
    
    uint Engine (uint Message)
    {
      if(State->Trigger())
      {
        State->Action();
        State = State->Next_state;
      }
    …
    }

    , чувствуете разницу?

    Единственное что могут возразить сторонники сверхформализма – при обычном программировании меньше учёта, при автоматносхемотехническом способе все биты сосчитаны. На это я отвечу, что если возникает проблема с учётом какого-то параметра, стоит создать подавтомат, который будет заниматься учётом, и освободить основной автомат от рутины. Это совет по конструктивной декомпозиции.

    Драматизм ситуации, связанной с программатами, в том то и состоит, что автоматный ментальный шаблон, давая удобный инструмент моделирования и анализа динамических процессов, одновременно тяжёлой дланью доминирует над разработчиками, лишая их простых радостей обычного программирования. Это на мой взгляд одна из самых серьёзных причин того, что технология автоматного программирования не может подняться выше чем экзотическая диковинка.

    Как несложно догадаться, естественный путь преодоления этой противоречивой ситуации — взять лучшее от обеих парадигм. В этом случае внутреннее состояние становится не столько указанием как обрабатывать следующее входящее событие, но оно становятся неким режимом работы. Это важно. Состояние скорей следует рассматривать как подпрограмму, в которой алгоритм находится некоторое время. При этом он может обрабатывать входные сигналы, транслировать их в выходные, никуда не переходя. Подразумевается, что в одном состоянии программат выполняет однотипную работу, всё что выходит за рамки однотипности переносится в другое состояние. Переход из состояния в состояние производится не любым сигналом, а только значимыми для этого алгоритма событиями. И эти события мы выбираем сами, исходя из выбранных нами же состояний. И соответственно, каждое состояние-режим может содержать вложенные программаты.

    image

    Рисунок 6. Конструктивный шаблон, при котором состояние это режим работы.

    Но программат не находится монопольно в функции-режиме до тех пока не совершит переход. Он выполняет короткие итерации, в ходе которых контролирует обстановку. При этом приложение в целом выглядит как:

    image

    Рисунок 7. Сообщество программатов.

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

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

    image

    Рисунок 8. Программаты в многопоточной среде.

    Поскольку программат может выполнять однократные действия, происходящие при совершении перехода, а может совершать протяжённую деятельность, находясь в одном и том же состоянии — режиме работы, то его диаграмма состояний приобретает черты и автоматов Мили и автоматов Мура. Например автомат парковочный счётчик, описывается диаграммой состояний.

    image

    Рисунок 9. Программат «Парковочный счётчик», описание совмещает черты автоматов Мили и Мура.

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

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

    Описанное проливает немного света на то, чем являются программаты, перейдём к способам их реализации.

    Способы реализации функциональных программных автоматов.


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

    image

    Рисунок 10. Граф-схема, которую требуется реализовать.

    Самое очевидное, вытекающее напрямую из граф-схемы решение «в лоб», – использовать для определения состояния конструкцию множественной альтернативы языка Си, оператор switch. При получении очередного входного символа программа определяет текущее состояние, и для каждого состояния проводится анализ входного символа, при этом для каждого входного символа задан не только переход в определённое состояние, но и выходной символ.

    Вариант 1.
    
    #define mStep ((uword) (-2))// см. далее
    
    uint Automaton (uint Input)
    {
    
      static uint State = 3;
      uint Out;
      
      {действия, которые выполняются и без переходов, если требуются };   
      
      switch (State)
      {
        
      ////////////////////////////////////////////  
      case 1:
        
        switch (Input)
        {    
        /////////// 
        case 0:      
          {дополнительные действия, если требуются };   
          State = 2;  
          Out = 2;
          break;      
        /////////// 
        case 1:
          {дополнительные действия, если требуются };   
          State = 3;
          Out = 3;      
          break;      
        /////////// 
        case 2:     
          {дополнительные действия, если требуются };   
          State = 6;
          Out = 6;      
          break;    
        /////////// 
        case mStep:
          break;    
        }
        
        break;
        
      ////////////////////////////////////////////  
      case 2:
        ...
      ////////////////////////////////////////////  
      case 3:
        ...
      ////////////////////////////////////////////  
      case 4:
        ...
      ////////////////////////////////////////////  
      case 5:
        ...
      ////////////////////////////////////////////  
      case 6:
        ...
      default:
       // Error
        
      };
    
      return(Out);
    
    }


    Подобными способами реализованы автоматы в Switch-технология и в IAR visualState.

    Поскольку концепция состояний программата трактует их как режимы работы программы, в которых та может некоторое время функционировать, не совершая переходов, но в то же время продолжая свою «мелкую деятельность», то должен быть входной символ, который гарантированно не переводит программат в новое состояние (если только он не перейдёт сам, по внутренним причинам), однако активирует его каждую итерацию. Символ шаг – mStep.

    Второй вариант реализации, принципиально отличающийся: сделать обработчик каждого события, как это показано на листинге

    Вариант 2.
    
    uint Message_i0_handler(uint &State)
    {
    
      uint Out;
    
      switch (State)
      {
        
      ////////////////////////////////////////////  
      case 1:
        {дополнительные действия, если требуются };   
        State = 2;
        Out = 2;      
        break;   
      ////////////////////////////////////////////  
      case 2:
        {дополнительные действия, если требуются };   
        State = 1;
        Out = 1;      
        break;    
    
      ... 
    
      };
    
      return(Out);
    
    
    }
    
    uint Message_i1_handler(uint &State)
    {
      ...
    }
    
    uint Message_i2_handler(uint &State)
    {
      ...
    }
    
    void Message_Step_handler(uint &State)
    {
    
        switch (State)
      {
        
      ////////////////////////////////////////////  
      case 1: 
        {действия, которые выполняются и без переходов, если требуются };   
        break;     
      ////////////////////////////////////////////  
      case 2: 
        {действия, которые выполняются и без переходов, если требуются };   
        break;      
      ////////////////////////////////////////////  
      case 3: 
        {действия, которые выполняются и без переходов, если требуются };   
        break;  
    
      };
    
      return(mStep);
    
    }
    
    
    
    typedef uint (*paMessage_handler)(uint &State);
    
    paMessage_handler Reactions[3] = { Message_i0_handler_for_s1, Message_i1_handler_for_s1, Message_i2_handler_for_s1};
    
    
    
    uint Automaton (uint Input)
    {
    
      Reactions [Input];
    
    }


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

    Модифицируем код, приведённый на листинге Вариант 2. Разобьём каждый обработчик событий Message_ixx_handler на набор функций, соответствующих каждому состоянию

    Вариант 3.
    
    uint Message_i0_handler_for_s1(uint &State)
    {
    
        {дополнительные действия, если требуются };   
        State = 2;
        Out = 2;      
    
      return(Out);
    
    }
    
    uint Message_i0_handler_for_s2(uint &State)
    {
    
        {дополнительные действия, если требуются };   
        State = 1;
        Out = 1;      
    
      return(Out);
    
    }
    ...
    
    uint Message_Step_handler_for_s1(uint &State)
    {
      {действия, которые выполняются и без переходов, если требуются };   
      return(mStep);
    
    }

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

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

    typedef uint (*paMessage_handler)(uint &State);
    
    paMessage_handler Reactions[6][3] = {
    
    { Message_i0_handler_for_s1, Message_i1_handler_for_s1, Message_i2_handler_for_s1},
    ...
    { Message_i0_handler_for_s6, Message_i1_handler_for_s6, Message_i2_handler_for_s6},
    
    
    };
    
    paMessage_handler Reactions_for_Step [6] = { Message_mStep_handler_for_s1, ..., Message_mStep_handler_for_s6 };
    
    
    uint Engine(uint Input = mStep)
    {
    
      uint State = 3;
     
      if(Input == mStep)
        
        return(Reactions_for_Step [State] (State));
    
      else
    
        return(Reactions[State][Input] (State));
    
    }


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

    Схожий способ лежит в основе реализации шаблона boost.statechart.

    Основной недостаток предыдущих двух вариантов: они артефакты автоматной схемотехники, то есть программируя таким образом, невозможно сохранить «программистский стиль» программирования, приходится использовать табличный стиль программирования, чрезмерно раздутый.

    Рассмотрим что даёт табличный стиль программирования:

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

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

    Гораздо более благодатным в плане возможностей для модификации оказывается вариант приведённый на листинге Вариант 1, если его расширить принятой концепцией состояний-режимов работы.

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

    Вариант 4.
    
    uint State_1 (uint &State, uint Input)
    {
    
      {действия, которые выполняются и без переходов, если требуются };   
    
      switch (Input)
      {    
      /////////// 
      case 0:      
        {дополнительные действия, если требуется };   
        State = 2;  
        Out = 2;
        break;      
      /////////// 
      case 1:
        {дополнительные действия, если требуется };   
        State = 3;
        Out = 3;      
        break;      
      /////////// 
      case 2:     
        {дополнительные действия, если требуется };   
        State = 6;
        Out = 6;      
        break;        
      /////////// 
      case mStep:  
        // Ничего не делаем       
    };
    
    uint State_2 (uint &State, uint Input){...};


    Все свежевычлененные функции-состояния поместим в массив, чтобы функцию-состояние можно было указать её индексом. Тогда переменная Внутреннее состояние это индекс, значение типа uint, а движок принимает вид

    
    typedef uint (*paState)(uint &State, uint Input);
    
    paState States[6] = {
    
    { State_1, ..., State_6},
    
    };
    
    uint Engine(uint Input = mStep)
    {
    
      static uint State = 3;
     
      return(States [State] (State, Input));
    
    }


    При кажущемся сходстве с вариантом 3, этот больше соответствует концепции программата, как набора сменяющихся режимов. Каждая функция-состояние это функция-режим, которая сама опрашивает всю требуемую ей периферию, или засинхронизованный кадр данных из периферии, и совершает переходы на основании этого, а не только на основании символа Input.

    Символ Input при этом может содержать однотипные для всех программатов системные сообщения. Это означает в частности, что сама функция-состояние может быть написана традиционным, максимально привычным способом.

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

    Хотя этот вариант более скоростной, количество рутины не сокращается. Главный минус этой реализации в том, что нужно иметь и таблицу состояний, и вести параллельный учёт состояний в заголовочнике и в файле кода, причём не copy/paste, так сказать проблема двойного описания. Однако и эта проблема решается довольно просто. Модифицируем указанный пример. Вместо переменной Внутреннее состояние, которая есть индекс указателя в константной таблице, можно использовать переменную Внутреннее состояние, которая сама и является указателем на функцию-состояние:

    Вариант 5.
    
    typedef uint (*paState)( void * argState, uint Input);
    
    uint State_1 (paState * State, uint Input)
    {
    
      {действия, которые выполняются и без переходов, если требуются };   
    
      switch (Input)
      {    
      /////////// 
      case 0:      
        {дополнительные действия, если требуется };   
        State = (paState*) State_2;  
        Out = 2;
        break;      
      /////////// 
      case 1:
        {дополнительные действия, если требуется };   
        State = (paState*) State_3;  
        Out = 3;      
        break;      
      /////////// 
      case 2:     
        {дополнительные действия, если требуется };   
        State = (paState*) State_6;  
        Out = 6;      
        break;        
      /////////// 
      case mStep:  
        // Ничего не делаем       
    
    
    };
    uint State_2 (paState *State, uint Input){...};
    
    uint Engine(uint Input = mStep)
    {
    
      static paState *State = (paState*) State_3;
     
      return(State(State, Input));
    
    }


    Описанный вариант уже почти не отличается от «естественного» программирования. Это становится ещё очевидней, если представить, что внутри конструкций switch и даже вместо них можно использовать конструкции типа

    
    if(IO_latch->Data_1_received && IO_latch->Permission)
    {
      State = 5;
    }

    От «естественного» программирования этот вариант отличается только тем, что отдельные состояния-режимы вынесены в отдельные функции. Однако, разбиение задачи на простые подзадачи-функции это один из основных приёмов любого программирования. Здесь же речь идёт только о том, что есть конструктивный критерий разбиения программы (отдельное состояние — отдельная функция), позволяющий избежать механистического, наивного дробления исходного кода: эта функция получилась большая, разделим её, например, по диагонали. Я утрирую, но когда нет критерия разбиения, оно будет либо скатываться в крайности (любой чих — отдельная функция), либо будет производиться на основе некоторого внутреннего чувства правильности происходящего, которое тренируется годами и даже тут автоматный способ представления процессов отличная помощь воображению, посколько удачно «структурирует поток сознания» в процессе разработки.

    Ярким примером «естественного», но автоматного программирования является автомат tDisplay::Out_text, из «Введения». Этот автомат описывается диаграммой состояний и переходов.

    image

    Рисунок 11. Диаграмма состояний и переходов автомата разбиения текста на блоки


    Вариант 6. Исходник автомата разбиения текста.
    image


    Как видно из этого примера, все состояния вполне можно реализовать в виде одной функции. В этом примере нет необходимости использовать оператор goto, но я добавил его к имеющимся классическими структурными конструкциями — ветвлениями и циклу. Это сама по себе ещё одна структурная конструкция программирования — переход в состояние автомата. Пару слов подробней об этой структурной конструкции.

    В общем случае каждое состояние помечено меткой а переходы между состояниями выполняются при помощи структурной конструкции goto Имя_метки_состояния;

    Состояние всегда начинается с метки, программа не может попасть внутрь состояния иначе как через его входную точку. Их даже можно заключить в скобки {}, и могут быть вложенные автоматы внутри одной функции(!). Но это уже чересчур. Так обеспечивается соблюдение принципа модульности, даже при работе внутри единственной функции, поэтому ничто не нарушает принципов надёжного программирования допуская использование операторов goto. Все переходы совершаются в полном соответствии с диаграммой состояний. Это позволяет вносить изменения без повышения сложности, всё как бы разложено по полочкам и ничего лишнего.

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

          
    
    typedef uint (*paState)( void * argState, uint Input);
    
    #define mGoto(argState,argOut){\
    State = (paState*)argState;\
    return(argOut);\
    }
    
    #define mStall_code ( (uword)(-1) )
    #define mStall(){\
    return(mStall_code);\
    }
    
    //Должен периодически запускаться 
    uint Engine(paState *State, uint Input = mStep)
    {
      
      return(State(State, Input));
    
    }
    

    Этот несложный API позволяет управлять поведением автомата из функций-состояний этого же автомата.

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

    Использование описанной системы команд выполняется по схеме.

    Вариант 7
    
    paState *Display_state; 
    
    void tDisplay::Out_text (int arg_x0, int arg_y0,
                             int arg_x1, int arg_y1,
                             int arg_x_shift, int arg_y_shift,
                             unsigned char * argText,
                             TMemo * argDebug)
    {
    
       // Инициализация
              Display_state = (paState*) state__Inside_text_block; 
     
       // Движок
              while(Engine (Display_state, 0) != mStall_code);
    
              return;
     
    
    }//void tDisplay::Out_text (int arg_x0, int arg_y0,
      
    
      
    
    ////////////////////////////////////////////////////////////////////////////
           ////////////////////////////////////////////////////////////////////////////
           ////////////////////////////////////////////////////////////////////////////
    uint state__Inside_text_block(paState * State, uint Input)
    {
      
      if(Input == mForce_Out_text_block)
    
        mGoto(state__Out_text_block, 0);
    
    
      while(1)
      {
    
        switch(*Text_end)
        {
    
          case '\0':
          case '\n':
            mGoto(state__Out_text_block, 0);
    
        }
    
        Text_end++;
    
      }
      
    }// uint state__Inside_text_block(paState * State, uint Input)
    
      
    
    
    ////////////////////////////////////////////////////////////////////////////
           ////////////////////////////////////////////////////////////////////////////
           ////////////////////////////////////////////////////////////////////////////
    uint state__Out_text_block(paState * State, uint Input)
    {
    
      if(Text != Text_end)
      {
    
        // Вложенный вызов операционного автомата.
        Out_text_block();
    
        // После выполнения Execute_script в Line_width фактическое количество выведенных пикселов
        x_rel += Line_width;
    
      }
    
      // Сброс буфера произведён
      Text = Text_end;
            
      mGoto(state__Control_processing, 0);
    
    
    }// uint state__Out_text_block(paState * State, uint Input)
    
    
    
    ////////////////////////////////////////////////////////////////////////////
    //////////////////////////////////////////////////////////////////////////       ////////////////////////////////////////////////////////////////////////////
    uint state__Control_processing(paState * State, uint Input)
    {
    
      if(*Text_begin == 0)
      {
    
        mStall();
    
      }
    
             // Обработка esc последовательности
    
      mGoto(state__Control_processing, 0);
    
    }
    


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

    Описанный простой API очень удобен и весьма функционален. С его помощью можно модифицировать пример 4, и он будет выглядеть следующим образом. Движок тот же что и для варианта 4.

    Вариант 8
    uint State_1 (paState * State, uint Input)
    {
    
      {действия, которые выполняются и без переходов, если требуются };   
    
      switch (Input)
      {    
      /////////// 
      case 0:      
    
        {дополнительные действия, если требуется };   
        mGoto(State_2,2);
    
      /////////// 
      case 1:
    
        {дополнительные действия, если требуется };   
        mGoto(State_3,3);
    
    
      /////////// 
      case 2:     
    
        {дополнительные действия, если требуется };   
        mGoto(State_6,6);
    
      /////////// 
      case mStep:  
        // Ничего не делаем.   
    
      return (0);
    
    };


    Этот API удобен в практическом применении, несмотря на простоту охватывает огромную часть потребностей автоматосоставления.

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

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

    Способы реализации символьных программных автоматов.


    Напоследок рассмотрим способы реализации простых символьных автоматов. Как было сказано выше, они образуют отдельное семейство, их концепция серьёзно отличается от функциональных автоматов, они являются классическими абстрактными автоматами, и способы реализации двух семейств автоматов отличаются, хотя имеют общие черты. Пусть имеется автомат, на вход которого поступает последовательность символов a,b,c, и который выдаёт 1 в случае, когда обнаруживает указанную последовательность, и 0 во все остальных случаях.

    Пусть искомая последовательность bacab. Диаграмма состояний этого автомата изображена на рис. 12

    image

    Рисунок 12. Автомат определения входной последовательности bacab.

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

    uint FSM[States_amount][Alphabet_size];
    

    в котором каждый вложенный массив соответствует состоянию, а каждый элемент вложенного массива содержит индекс следующего состояния для каждого входного символа. Каждому входному символу, в общем случае сопоставляется индекс от 0 до Размер_алфавита – 1. Этот массив – классическая таблица переходов автомата. Поскольку выходной символ всегда 0, кроме единственного случая «код распознан», то таблицу выходов можно не создавать, но в случае, когда код распознан, в ячейке таблицы вместо следующего состояния, значения 0, 1,2, … будет стоять число 0xff..ff. В этом случае код возврата из движка 1, а индекс следующего состояния 0.

    Движок таких автоматов описывается простой функцией, без комментариев.

    
    uint FSM[States_amount][Alphabet_size];
    
    uint Engine(uint Input)
    {
    
      static uint State = 0;
     
      State = FSM[State][Index_for(Input)];
    
      if(State == (uint)(-1))
    
      {
        State = 0;
        return 1;
      }
      else
      
        return 0;
    }
    
    
    // Использование в прикладной функции
    while(!terminate)
    {
      if(Engine(Stream++))
        goto Found;
    };
    Stopped:
    // Последовательность не обнаружена, работа остановлена командой
    
    Found:
    // Последовательность обнаружена
    }

    Я привёл основные способы реализации автоматов. Дальнейшее развитие способов реализации связано с соединениями автоматов. Это отдельная большая тема и ей будет посвящён отдельный цикл статей.

    Сегодняшний обзор подошёл к концу. В следующей статье речь пойдёт об эффективности – о тех плюсах, которые можно измерить.
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 20
    • 0
      >> АП не стало магистральным трендом. Главная причина здесь — недостаточный опыт использования ( часть №1)
      ну не только это, главная причина в том что автоматное программирование довольно нишевое, и не везде его можно и не всегда целесообразно применять

      и даже тогда когда есть смысл есть много моментов
      например в схеме анализа bacab слишком много линий, это при том, что последовательность простая. стоит появится множественным линиям ( как уже не раз на хабре отмечалось ) получается полный швах. конечно, можно применить элементы концентраторы, которые помогут сделать схему читаемой. но так же можно отметить, что проблема неявных переходов остаётся, и плодить лишние стрелки тут совсем уже плохо.
      вот ваш пример c bacab
      скрытая картинка
      image

      на ней голубым цветом как раз концентраторы.
      тут немножко кода
      W=703
      switch(W)
      {
      case 703:
      if (S==«b»){W=704;continue;}
      return;
      case 704:
      if (S==«a»){W=705;continue;}
      return;
      case 705:
      if (S==«c»){W=706;continue;}
      return;
      case 706:
      if (S==«a»){W=708;continue;}
      if (S==«E»){W=712;continue;}
      return;
      case 707: return;
      case 708:
      if (S==«b»){W=707;continue;}
      return;
      case 710: return;
      case 712:
      if (S==«b»){W=707;continue;}
      return;
      default: return;
      }


      у Вас не заметно 2 важных аспекта
      — то что если схема порождает код — значит ошибок на этом участке нет и всё точно,
      — то что схема позволяет строить более сложные переходы проще. на моей блок схеме добавлена буква Е. А вот добавить это условие в привычный код намного сложнее.

      но как показала практика блок схемы это всё же крайне нишевое решение. потому в других местах это становится тупиковым направлением, даже если кажется, что есть какие-то преимущества.
      • 0
        у Вас не заметно 2 важных аспекта
        — то что если схема порождает код — значит ошибок на этом участке нет и всё точно,

        Не уверен, что правильно Вас понимаю, поясните пожалуйста что значит «схема порождает код»?

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

        И что получается, автомат который теперь определяет 2 кода: bacab и bacEb? Или пардон?

        причина в том что автоматное программирование довольно нишевое, и не везде его можно и не всегда целесообразно применять

        Если не попадать под влияние распространённых стереотипов, о которых рассказано в пункте «Артефакты автоматной схемотехники» автоматное программирование очень похоже на «естественное» программирование. Основное отличие — в проектировании. Я это буду демонстрировать на примерах.
        • 0
          Если не попадать под влияние распространённых стереотипов

          не знаю, я не попадаю, просто практика и удобство применения говорит что не так всё просто и радужно как может показаться на первый взгляд
          «схема порождает код»

          как изображено, ровно так и будет реализовано. а иначе зачем? не красоваться же.
          И что получается, автомат который теперь определяет 2 кода: bacab и bacEb?

          ну да, в коде вроде это должно быть понятно
          if (S==«a»){W=708;continue;}
          if (S==«E»){W=712;continue;}

          можно например добавить ещё немного и получить
          новая схема
          image

          эта схема определяет
          bacab и bacEb
          + bacE,bacE1,bacE12
          и порождающий код будет точно соответствовать схеме.

          • +1
            *такую программу можно нужно реализовывать не через switсh, а через таблицы, это не только работает работает быстрее, но и:
            *эти таблицы составляются автоматически, я приведу пример. Диаграмму состояний я нарисовал как пример. Для символьных автоматов диаграммы в процессе разработки не нужны. Я приведу программу, которая составляет таблицы
            * автоматы распознающие коды, точнее определяющий один из нескольких возможных это интересная тема, у меня есть. Вообще символьным автоматам я собираюсь посвятить отдельную статью.
            * диаграммы состояния составляются для функциональных автоматов. В этом случае диаграмма состояний замечательно описывает процесс. Например рисунок 3 в тексте статьи.

            И позвольте задать Вам вопрос как читателю. Достаточно ли я провёл разделение автоматов на символьные и функциональные, или оно не выглядит столь фундаментальным? Дело в том, что я хочу направить внимание читателей на то, что акцент будет на функциональные автоматы и описание при помощи диаграммы состояний именно алгоритмов, а не символьных автоматов, которые получаются алгоритмически и хранятся в виде таблиц

            «схема порождает код» — как изображено, ровно так и будет реализовано. а иначе зачем? не красоваться же.

            Тогда поясните фразу
            — то что если схема порождает код — значит ошибок на этом участке нет и всё точно,

            лучше с примером
            • 0
              Тогда поясните фразу — то что если схема порождает код

              ну как бы я уже приводил пример, повторю
              схема и соответствующий код
              image
              в точности порождает
              W=703
              switch(W)
              {
              case 703:
              if (S==«b»){W=704;continue;}
              return;
              case 704:
              if (S==«a»){W=705;continue;}
              return;
              case 705:
              if (S==«c»){W=706;continue;}
              return;
              case 706:
              if (S==«a»){W=708;continue;}
              if (S==«E»){W=712;continue;}
              return;
              case 707: return;
              case 708:
              if (S==«b»){W=707;continue;}
              return;
              case 710: return;
              case 712:
              if (S==«b»){W=707;continue;}
              return;
              default: return;
              }
              это работающий код и мне не надо думать что реализуемое поведение будет отличаться от схемы. если на схеме стрелка идёт от 'с' к 'а' и к 'Е' то трассировка и проверка не нужна.


              разделение автоматов на символьные и функциональные, или оно не выглядит столь фундаментальным

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

              *такую программу можно нужно реализовывать не через switсh, а через таблицы, это не только работает работает быстрее, но и:

              ну switch используется по причине простой и понятной
              1. он реально быстр, быстрее if и таблиц с хешами и прочим. проблемы у него будут если повесить 1000 case на один switch. тут хэш будет быстрее.
              2. наглядность, если есть какая то ошибка, то в switch -case эту ошибку можно увидеть и отловить. в случае таблиц отладка затруднена. понять почему ветвление пошло по этому маршруту сложнее.
              • +1
                по мне, как пользователю подобных автоматов, нет особой разницы и те и те автоматы, просто для символьных одни условия, для функциональных другие. но само построение одинаково.


                Позвольте пример — если даже не рассматривать тему символьных автоматов вообще, то автоматное программирование это удобный способ записи алгоритмов

                image

                Я как практикующий автоматный программист почти не составляю символьные, кроме как для примеров, но я могу при помощи диаграммы состояний записать алгоритм(автомат), который по заданному коду будет составлять таблицу(то есть автомат, которой строит другие автоматы) для распознавания любого кода. И вот те автоматы будут состоять из таблицы составленной компьютером, то есть речь не идёт об ошибках, которые может допустить человек а потом можно и не увидеть. Но быстродействие варианта к примеру для рис 12 не сравнится по быстродействию с быстродействием switch. Но если нет преимуществ, тогда зачем? Поясню, использование этой конструкции не противоречит автоматному программированию, но зачем?
                Другое дело функциональные программные автоматы — их можно показать как пример 1 — пример 8 и среди них т.н. базовая конструктивная реализация самое то. Это из моей практике, могу подтвердить коллегам, что очень практичная в использовании и скоростная как я не знаю что.

                • 0
                  я могу при помощи диаграммы состояний записать алгоритм(автомат), который по заданному коду будет составлять таблицу

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

                  и не надо забывать, что у подобного подхода есть 2 крупных минуса
                  1. прерывания.
                  они плохо кладутся в диаграмму состояний.
                  как пример — реализация 3х кнопочных часов Элекстроника
                  фото часов
                  image

                  вроде эти часы конечный автомат, но вот диаграммами его не описать. придётся шаманить

                  2. многопоточность. как её впихивать в состояния?

                  и да, по switch-case
                  case позволяет прыгать с ветки на ветку. довольно удобная штука
                  switch(char)
                  {
                  case 'a': goto case 'b';
                  case 'b':…
                  }

                  • +1
                    про часы интересный пример, я возможно использую его для иллюстрации

                    многопоточность. как её впихивать в состояния?

                    хороший вопрос. для обмена прерывание-фон активно используются кольцевые буферы для обмена данными. автоматы висят в прерываниях (как показано на рис 7 )
                    • 0
                      я не про обмен данными, а про общую синхронизацию.
                      есть система, которая пребывает в каком то состоянии. у неё несколько фоновых потоков. + происходят прерывания.
                      и вот как это диаграммами однозначно запилить?
                      часы это похожий пример. есть кварцевой генератор тактов — фоновый поток. есть кнопки — прерыватели. в зависимости от порядка нажатий — на экране показывается разная инфа.
                      • +1
                        Вот здесь как предугадал, что вы напишите про диаграммы состояний. нет единой диаграммы состояний — есть сообщество программ — автоматов и всё. обмен данными через буферы, синхронизация через флаги, никаких проблем
                        + про часы я пожалуй сделаю пример
                        • –1
                          может быть я что то недопонял, диаграммы состояний с флагами нужны для чего
                          №1) для понимания процессов
                          №2) на основе графа зависимостей — построение программной реализации
                          из текста как я понял что речь идёт о п.№2, но как то очень лихо примешан буфер, флаги. Есть конкретное понимание как это работает, или это общее представление как должно быть.

                          мой моск плохо понимает, как скрестить в одном графе одновременно и состояния, и прерывания, и кольцевой буфер.
                          как общая картинка для понимания №1 — почему бы и нет,
                          а вот как №2 — создание модели непонимать. если у Вас есть такое понимание, готов выслушать.

                          • +1
                            мы же говорим об автоматной многозадачности? если вкрадце, то можно рассматривать автоматы как классы, обращение к которым идёт только через кольцевые буферы(каналы связи между процессами) которых может быть сколько угодно. Один автомат — один процесс. Не нужно составлять диаграмму состояний которая охватит все биты микроконтроллера — перечитайте раздел «Артефакты автоматной схемотехники», там же ответы на ваши вопросы, можно сказать, между строк. Но будет статья и я подчеркну этот факт, спасибо за интерес
                            • 0
                              мы говорим о подходе к созданию программ с использованием графа состояний. не так ли?
                              и подразумевается, что применение этого подхода должно значительно упростить процесс создания.
                              в «Артефакты автоматной схемотехники» не увидел между строк понимание сложных моментов — смеси разнородных вещей — самих состояний, буферов, потоков ( и!!! массива потоков )

                              там же сложность в том, что в одном случае стрелка означает одно, в другом другое. легко запутаться.

                              я когда то занимался автоматами, но перестал, т.к. понял ограниченную перспективу их реального применения. для каких то задач они идеальны, но их очень мало.
                              • +1
                                там же сложность в том, что в одном случае стрелка означает одно, в другом другое. легко запутаться.

                                над стрелками однозначные подписи, это психологический аспект: это кажется непривычным и поэтому малопонимаемым вообще, но это не так
                                я учту то что Вы написали, я отвечу статьёй с картинками, так будет понятней.
                                • 0
                                  Как подписи у стрелок отождествляют код. Или это просто информативный текст?
                                  • +1
                                    далее я рассчитываю показывать примеры автоматов, буду акцентировать внимание на способы воплощения в коде.
                                    • 0
                                      когда ждать статью? предыдущая статья датируется июнем. хотя прекрасно понимаю, что тема не простая.

                                      Будет интересно посмотреть альтернативный подход.
                                    • +1
                                      Это текст, которым я в процессе проектирования автомата описываю алгоритм, неформально но однозначно. А как полученную диаграмму состояний обратить в алгоритм, это уже вопрос освещённый.
                      • +1
                        1. прерывания.
                        они плохо кладутся в диаграмму состояний.

                        это в общем дополнение к коменту выше — не составляется единый автомат всего программного процесса — всё разбивается на ряд подавтоматов, часть из которых висит в прерывании часть в фоне, обмен межу которыми через структуры данных — кольцевые буферы самый универсальный вариант
          • 0
            del

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.