✖


Jump to content

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

Другие варианты использования см. в разделе « Программирование на основе автоматов (подход Шалито)» .

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

Программирование на основе конечных автоматов в целом одно и то же, но, формально говоря, не охватывает все возможные варианты, поскольку 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;
}

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

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

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

Таблица перехода состояний
Вход
Текущее состояние
новая строка пробелы другой
до до до внутри/распечатать
внутри до/распечатать после внутри/распечатать
после до/распечатать после после
Диаграмма состояний
Диаграмма состояний конечного автомата, который печатает первое слово каждой строки входного потока. На каждом шаге машина выполняет ровно один переход, в зависимости от текущего состояния и встреченного персонажа. Действием, сопровождающим переход, является либо отказ от операции, либо печать встреченного символа, обозначаемая 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;
}

Автоматика и автоматы [ править ]

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

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

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

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

Программа автоматизации [ править ]

Представленный выше пример может быть выражен в соответствии с этим представлением, как в следующем псевдокоде («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

Приложения [ править ]

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

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

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

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

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

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

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

История [ править ]

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

Одна из первых работ по этому вопросу принадлежит Johnson et al., 1968. [3]

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

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

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

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

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

Внешние ссылки [ править ]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Automata-based_programming&oldid=1202040203"
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 6ca11b638b7250a201d482470e9a54f9__1706816280
URL1:https://arc.ask3.ru/arc/aa/6c/f9/6ca11b638b7250a201d482470e9a54f9.html
Заголовок, (Title) документа по адресу, URL1:
Automata-based programming - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)