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

Чтобы узнать о других значениях, см. Программирование на основе автоматов (подход Шалыто) .
Парадигмы программирования

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

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

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

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

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

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

Пример

Задача

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

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

Традиционная программа на 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;
}

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

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

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

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

Вообще говоря, автоматная программа, естественно, может использовать этот подход. С явным двумерным массивом 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функции из стандартной библиотеки Си .

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

#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;
}

Автоматика и автоматы

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

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

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

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

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

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

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

Приложения

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

использованная литература

  1. ^ a b Ахо, Альфред В .; Ульман, Джеффри Д. (1973). Теория разбора, перевода и компиляции . 1 . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. ISBN  0-13-914564-8.
  2. ^ Ollongren, Александр (1974). Определение языков программирования путем интерпретации автоматов . Лондон: Academic Press. ISBN 0-12-525750-3.
  3. ^ Джонсон, WL; Портер, JH; Экли, С.И.; Росс, Д.Т. (1968). «Автоматическая генерация эффективных лексических процессоров с использованием методов конечного состояния». Связь ACM . 11 (12): 805–813. DOI : 10.1145 / 364175.364185 . S2CID 17253809 .  
  4. ↑ Наур, Питер (сентябрь 1963 г.). "Дизайн компилятора GIER ALGOL Часть II". BIT Численная математика . 3 (3): 145–166. DOI : 10.1007 / BF01939983 . S2CID 189785656 .  
  5. ^ "Автоматное программирование" (PDF) . Научно-технический журнал информационных технологий, механики и оптики (53). 2008 г.

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