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

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

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

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

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

Все выполнение кода на основе автоматов представляет собой цикл шагов Automaton.

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

Пример

Задача

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

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

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

#include <ctype.h>
#include <stdio.h>


int main(void) {
  int c;

  do {
    do {
      c = getchar();
    } while (isspace(c));

    while (!isspace(c) && c != EOF) {
      putchar(c);
      c = getchar();
    }
    
    while (c != '\n' && c != EOF) {
      c = getchar();
    }
    
    if (c == '\n') {
      putchar(c);
    }
  } while (c != EOF);

  return 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)

Доходность:

foo
qux

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

Процедурный

Та же самая задача может быть решена путем мышления с точки зрения конечных штатных машин . Проанализирование линии имеет три этапа: пропуская ведущие персонажи пробела, печатаю персонажей первого слова и пропуская трюки. Назовем эти штаты автомата BEFORE, INSIDE и AFTERПолем Версия программы на основе автоматов может выглядеть так:

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    switch (s) {
      case BEFORE:
        if (!isspace(c)) {
          putchar(c);
          s = INSIDE;
        }
        
        break;
      case INSIDE:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        } else if (isspace(c)) {
          s = AFTER;
        } else {
          putchar(c);
        }
          
        break;
      case AFTER:
        if (c == '\n') {
          putchar(c);
          s = BEFORE;
        }
        
        break;
    }
  }

  return 0;
}

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

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

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


void step(enum State* const s, int const c) {
  switch (*s) {
    case BEFORE:
      if (!isspace(c)) {
        putchar(c);
        *s = INSIDE;
      }
      
      break;
    case INSIDE:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      } else if (isspace(c)) {
        *s = AFTER;
      } else {
        putchar(c);
      }
        
      break;
    case AFTER:
      if (c == '\n') {
        putchar(c);
        *s = BEFORE;
      }
      
      break;
  }
}


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    step(&s, c);
  }

  return 0;
}

Программа теперь четко демонстрирует основные свойства кода на основе автоматов:

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

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

Таблица трансляции государства
Вход Текущее состояние	новая линия	пробел	другой
до	до	до	Внутри/Печать
внутри	до/print	после	Внутри/Печать
после	до/print	после	после

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

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

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


void nop(int const c) {}


void print(int const c) {
  putchar(c);
}


struct Branch {
  enum State const next_state;
  void (*action)(int);
};


struct Branch const transitions[3][3] = {
  //   newline         whitespace         other             Inputs/States
  {{BEFORE,   &nop}, {BEFORE, &nop}, {INSIDE, &print}},  // before
  {{BEFORE, &print}, {AFTER,  &nop}, {INSIDE, &print}},  // inside
  {{BEFORE, &print}, {AFTER,  &nop}, {AFTER,    &nop}}   // after
};


void step(enum State* const s, int const c) {
  int const row = (*s == BEFORE) ? 0 : (*s == INSIDE) ? 1 : 2;
  int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
  struct Branch const* const b = &transitions[row][column];
  *s = b->next_state;
  b->action(c);
}


int main(void) {
  int c;
  enum State s = BEFORE;

  while ((c = getchar()) != EOF) {
    step(&s, c);
  }

  return 0;
}

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

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

#include <ctype.h>
#include <stdio.h>

enum State {BEFORE, INSIDE, AFTER};


struct Branch {
  enum State const next_state;
  void (*action)(int);
};


class StateMachine {
  public:
    StateMachine();
    void feedChar(int);

  protected:
    static void nop(int);
    static void print(int);

  private:
    enum State _state;
    static struct Branch const _transitions[3][3];
};


StateMachine::StateMachine(): _state(BEFORE) {}


void StateMachine::feedChar(int const c) {
  int const row = (_state == BEFORE) ? 0 : (_state == INSIDE) ? 1 : 2;
  int const column = (c == '\n') ? 0 : isspace(c) ? 1 : 2;
  struct Branch const* const b = &_transitions[row][column];
  _state = b->next_state;
  b->action(c);
}


void StateMachine::nop(int const c) {}


void StateMachine::print(int const c) {
  putchar(c);
}


struct Branch const StateMachine::_transitions[3][3] = {
  //   newline         whitespace         other             Inputs/States
  {{BEFORE,   &nop}, {BEFORE, &nop}, {INSIDE, &print}},  // before
  {{BEFORE, &print}, {AFTER,  &nop}, {INSIDE, &print}},  // inside
  {{BEFORE, &print}, {AFTER,  &nop}, {AFTER,    &nop}}   // after
};


int main() {
  int c;
  StateMachine m;

  while ((c = getchar()) != EOF) {
    m.feedChar(c);
  }

  return 0;
}

Чтобы свести к минимуму изменения, не связанные напрямую с предметом статьи, вход/вывод getchar и putchar Функции из стандартной библиотеки C используются.

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

#include <ctype.h>
#include <stdio.h>

class StateMachine;


class State {
  public:
    virtual void feedChar(StateMachine*, int) const = 0;
};


class Before: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    Before() = default;

  private:
    static State const* _instance;
};


class Inside: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    Inside() = default;

  private:
    static State const* _instance;
};


class After: public State {
  public:
    static State const* instantiate();
    virtual void feedChar(StateMachine*, int) const override;

  protected:
    After() = default;

  private:
    static State const* _instance;
};


class StateMachine {
  public:
    StateMachine();
    void feedChar(int);

  protected:
    void setState(State const*);

  private:
    State const* _state;
    friend class Before;
    friend class Inside;
    friend class After;
};


State const* Before::instantiate() {
  if (!_instance) {
    _instance = new Before;
  }

  return _instance;
}


void Before::feedChar(StateMachine* const m, int const c) const {
  if (!isspace(c)) {
    putchar(c);
    m->setState(Inside::instantiate());
  }
}


State const* Before::_instance = nullptr;


State const* Inside::instantiate() {
  if (!_instance) {
    _instance = new Inside;
  }

  return _instance;
}


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::instantiate());
  } else {
    putchar(c);
  }
}


State const* Inside::_instance = nullptr;


State const* After::instantiate() {
  if (!_instance) {
    _instance = new After;
  }

  return _instance;
}


void After::feedChar(StateMachine* const m, int const c) const {
  if (c == '\n') {
    putchar(c);
    m->setState(Before::instantiate());
  }
}


State const* After::_instance = nullptr;


StateMachine::StateMachine(): _state(Before::instantiate()) {}


void StateMachine::feedChar(int const c) {
  _state->feedChar(this, c);
}


void StateMachine::setState(State const* const s) {
  _state = s;
}


int main() {
  int c;
  StateMachine m;

  while ((c = getchar()) != EOF) {
    m.feedChar(c);
  }

  return 0;
}

Автоматизация и автоматическая

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

Производственный цикл обычно моделируется как:

последовательность этапов, шагающих в соответствии с входными данными (от COFSTERS);
набор действий, выполненных в зависимости от текущей стадии.

Различные выделенные языки программирования позволяют выражать такую модель более или менее сложными способами.

Программа автоматизации

Пример, представленное выше, может быть выражен в соответствии с этой точкой зрения, как в следующем псевдо-коде («установить» активирует логическую переменную, «сбросить» инактивирует логическую переменную »:« назначает переменную и '=' тесты на равенство) :

newline: '\n'
whitespace: ('\t', '\n', '\v', '\f', '\r', ' ')
states: (before, inside, after)


setState(c) {
  if before and (c != newline and c not in whitespace) then set inside
  if inside then (if c in whitespace then set after else if c = newline then set before)
  if after and c = newline then set before
}


doAction(c) {
  if before and (c != newline and c not in whitespace) then write(c)
  if inside and c not in whitespace then write(c)
  if after and c = newline then write(c)
}


cycle {
  set before

  loop until (c: readCharacter) = EOL {
    setState(c)
    doAction(c)
  }
}

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

События

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

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

   s:stage   c:condition
   
   s1
   |
   |-c2
   |
   s2
   |
   ----------
   |        |
   |-c31    |-c32
   |        |
  s31       s32
   |        |
   |-c41    |-c42
   |        |
   ----------
   |
   s4

Приложения

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

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

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

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

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

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

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

История

Методы на основе автоматов широко использовались в доменах, где существуют алгоритмы, основанные на теории автоматов, таких как формальный анализ языка. ^{[ 1 ]}

Одна из ранних работ по этому поводу - Джонсон и др., 1968. ^{[ 3 ]}

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

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

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

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

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

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

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

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

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

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

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

Клеточный автомат
НЕТЕТЕРИНГИЧЕСКОЕ программирование
Государственный шаблон
Эестрил , АВТОМАЯ ЯЗЫКА
Umple , инструмент для добавления автоматов в Java и C ++

Ссылки

^ Jump up to: ^а ^{беременный} Ахо, Альфред В.; Уллман, Джеффри Д. (1973). Теория разбора, перевода и компиляции . Тол. 1. Englewood Cliffs, NJ: Prentice-Hall. ISBN 0-13-914564-8 .
^ Оллонгрен, Александр (1974). Определение языков программирования путем интерпретации автоматов . Лондон: академическая пресса. ISBN 0-12-525750-3 .
^ Джонсон, WL; Портер, JH; Экли, Си; Росс, Д.Т. (1968). «Автоматическая генерация эффективных лексических процессоров с использованием методов конечных состояний» . Comm Acm . 11 (12): 805–813. doi : 10.1145/364175.364185 . S2CID 17253809 .
^ Наур, Питер (сентябрь 1963 г.). «Дизайн Gier Algol Compiler Part II». Несколько численная математика . 3 (3): 145–166. doi : 10.1007/bf01939983 . S2CID 189785656 .
^ «Программирование на основе автоматов» (PDF) . Научный и технический журнал информационных технологий, механиков и оптики (53). 2008

Внешние ссылки

JV Noble. «Конечные государственные машины в Форт» на основе автоматов -Программирование
Harel, David (1987). «StateCharts: визуальный формализм для сложных систем» (PDF) . Наука Вычислительный Программирование . 8 (3): 231–274. doi : 10.1016/0167-6423 (87) 90035-9 .
Харел, Дэвид; Друзинский Д. (1989). «Использование StateCharts для описания оборудования и синтеза». IEEE транзакции по компьютерному проектированию интегрированных цепей и систем . 8 (7): 798–807. doi : 10.1109/43.31537 . S2CID 8754800 .
Polikarpova N. I., Shalyto A. A. Automata-based programming SPb.: Piter. 2009 (rus)
Университет ITMO, «Отдел технологий программирования»

[gram-1] Jump up to: ^а ^{беременный} Ахо, Альфред В.; Уллман, Джеффри Д. (1973). Теория разбора, перевода и компиляции . Тол. 1. Englewood Cliffs, NJ: Prentice-Hall. ISBN 0-13-914564-8 .

[2] Оллонгрен, Александр (1974). Определение языков программирования путем интерпретации автоматов . Лондон: академическая пресса. ISBN 0-12-525750-3 .

[3] Джонсон, WL; Портер, JH; Экли, Си; Росс, Д.Т. (1968). «Автоматическая генерация эффективных лексических процессоров с использованием методов конечных состояний» . Comm Acm . 11 (12): 805–813. doi : 10.1145/364175.364185 . S2CID 17253809 .

[4] Наур, Питер (сентябрь 1963 г.). «Дизайн Gier Algol Compiler Part II». Несколько численная математика . 3 (3): 145–166. doi : 10.1007/bf01939983 . S2CID 189785656 .

[5] «Программирование на основе автоматов» (PDF) . Научный и технический журнал информационных технологий, механиков и оптики (53). 2008

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]