Programação baseada em autômatos - Automata-based programming

A programação baseada em autômatos é um paradigma de programação no qual o programa ou parte dele é pensado como um modelo de uma máquina de estados finitos (FSM) ou qualquer outro autômato formal (geralmente mais complicado) (ver teoria dos autômatos ). Às vezes, um conjunto potencialmente infinito de estados possíveis é introduzido, e tal conjunto pode ter uma estrutura complicada, não apenas uma enumeração.

A programação baseada em máquina de estado finito é geralmente a mesma, mas, formalmente falando, não cobre todas as variantes possíveis, já que FSM significa máquina de estado finito, e a programação baseada em autômato não necessariamente emprega FSMs no sentido estrito.

As propriedades a seguir são indicadores-chave para a programação baseada em autômatos:

• O período de tempo de execução do programa é claramente separado nas etapas do autômato . Cada etapa é efetivamente uma execução de uma seção de código (igual para todas as etapas) que possui um único ponto de entrada. Essa seção pode ser dividida em subseções a serem executadas dependendo dos diferentes estados, embora isso não seja necessário.
• Qualquer comunicação entre as etapas do autômato só é possível por meio do conjunto de variáveis ​​explicitamente anotado denominado estado do autômato . Entre quaisquer duas etapas, o programa não pode ter componentes implícitos de seu estado, como valores de variáveis ​​locais, endereços de retorno, o ponteiro de instrução atual, etc. Ou seja, o estado de todo o programa, obtido em quaisquer dois momentos após a entrada de um passo do autômato, só pode diferir nos valores das variáveis ​​sendo consideradas como o estado do autômato.

Toda a execução do código baseado em autômatos é um ciclo das etapas do autômato.

Outra razão para usar a noção de programação baseada em autômatos é que o estilo de pensamento do programador sobre o programa nesta técnica é muito semelhante ao estilo de pensamento usado para resolver tarefas matemáticas usando máquinas de Turing , algoritmos de Markov , etc.

Exemplo

Tarefa

Considere a tarefa de ler um texto da entrada padrão linha por linha e escrever a primeira palavra de cada linha na saída padrão . Primeiro, pulamos todos os caracteres de espaço em branco iniciais , se houver. Em seguida, imprimimos todos os caracteres da primeira palavra. Finalmente, pulamos todos os caracteres finais até que um caractere de nova linha seja encontrado. Sempre que uma sequência de caracteres de nova linha não é encontrada no início do fluxo, imprimimos apenas o primeiro e pulamos os restantes; caso contrário, pulamos todos. Em seguida, reiniciamos o processo na linha seguinte. Ao encontrar a condição de fim de arquivo (independentemente do estágio), paramos.

Programa tradicional

Um programa tradicional em C que executa a tarefa acima pode ter a seguinte aparência:

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

Por exemplo, compilar e executar o programa acima nesta entrada:

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

rendimentos:

foo
qux

Programa baseado em autômatos

Processual

A mesma tarefa pode ser resolvida pensando em termos de máquinas de estado finito . Observe que a análise de uma linha tem três estágios: pular os caracteres de espaço em branco iniciais, imprimir os caracteres da primeira palavra e pular os caracteres finais. Vamos chamar esses estados autômato BEFORE, INSIDEe AFTER. Uma versão do programa baseada em autômatos pode ter a seguinte aparência:

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

Embora o programa agora pareça mais longo, ele tem pelo menos uma vantagem significativa: há apenas umagetchar instrução de leitura (ou seja, chamada para a função). Além disso, existe apenas um loop em vez dos quatro que a versão tradicional tinha. O corpo do whileloop é a etapa do autômato e o próprio loop é o ciclo da etapa do autômato. O programa implementa o trabalho de uma máquina de estados finitos mostrada no diagrama de estados.

A propriedade mais importante do programa é que a seção do código da etapa do autômato está claramente localizada. Com uma função explícita steppara a etapa de automação, o programa demonstra melhor esta propriedade:

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

O programa agora demonstra claramente as propriedades básicas do código baseado em autômatos:

• os períodos de tempo das execuções dos passos do autômato não podem se sobrepor;
• a única informação passada da etapa anterior para a próxima é o estado do autômato explicitamente especificado .

Um autômato finito pode ser definido por uma tabela de transição de estado cujas linhas representam os estados atuais, as colunas representam as entradas e as células representam os próximos estados e ações a serem executadas.

Diagrama de estado

O diagrama de estado de uma máquina de estados finitos que imprime a primeira palavra de cada linha de um fluxo de entrada. A máquina segue exatamente uma transição em cada etapa, dependendo do estado atual e do caractere encontrado. A ação que acompanha uma transição é uma não operação ou a impressão do caractere encontrado, denotado por impressão .

De modo geral, um programa baseado em autômatos pode naturalmente usar essa abordagem. Com uma matriz bidimensional explícita transitionspara a tabela de transição de estado, o programa usa esta abordagem:

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

Orientado a Objeto

Se a linguagem de implementação oferece suporte à programação orientada a objetos , uma refatoração simples do programa é encapsular o autômato em um objeto, ocultando assim seus detalhes de implementação. O programa em C ++ usando o estilo orientado a objetos pode ter a seguinte aparência:

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

Observação. - Para minimizar alterações não diretamente relacionadas ao assunto do artigo, a entrada / saída getchar e as putcharfunções da biblioteca padrão do C estão sendo usadas.

O padrão de design de estado é uma maneira de um objeto alterar seu comportamento em tempo de execução de acordo com seu estado interno, sem recorrer a grandes instruções condicionais ou pesquisas de tabela graças a chamadas de funções virtuais. Sua principal vantagem sobre o código que usa grandes instruções condicionais é que o código específico do estado é distribuído entre objetos diferentes, em vez de localizado em um bloco monolítico, o que melhora a capacidade de manutenção. Suas principais vantagens sobre o código que usa tabelas de transição de estado são que as chamadas de função virtual são geralmente mais eficientes do que as pesquisas de tabela, que os critérios de transição de estado são mais explícitos do que no formato tabular e que é mais fácil adicionar ações que acompanham as transições de estado. No entanto, isso introduz um novo problema: o número de classes torna o código menos compacto do que as outras abordagens. O programa que usa o padrão de design de estado pode ter a seguinte aparência:

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

Automação e autômatos

A programação baseada em autômatos realmente corresponde às necessidades de programação encontradas no campo da automação .

Um ciclo de produção é comumente modelado como:

• uma sequência de estágios escalonados de acordo com os dados de entrada (dos captores);
• um conjunto de ações realizadas dependendo do estágio atual.

Várias linguagens de programação dedicadas permitem expressar esse modelo de maneiras mais ou menos sofisticadas.

Programa de automação

O exemplo apresentado acima pode ser expresso de acordo com esta visão como no seguinte pseudocódigo ('definir' ativa uma variável lógica, 'redefinir' inativa uma variável lógica, ':' atribui uma variável e '=' testa a igualdade) :

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

A separação das rotinas que expressam a progressão do ciclo de um lado e a ação real do outro (correspondência de entrada e saída) permite um código mais claro e simples.

Eventos

No campo da automação, avançar passo a passo depende dos dados de entrada vindos da própria máquina. Isso é representado no programa pela leitura de caracteres de um texto. Na realidade, esses dados informam sobre a posição, velocidade, temperatura, etc. dos elementos críticos de uma máquina.

Como na programação GUI , as mudanças no estado da máquina podem ser consideradas como eventos que causam a passagem de um estado para outro, até que o estado final seja alcançado. A combinação de estados possíveis pode gerar uma grande variedade de eventos, definindo assim um ciclo de produção mais complexo. Como consequência, os ciclos geralmente são sequências lineares simples. Existem geralmente ramificações paralelas funcionando juntas e alternativas selecionadas de acordo com diferentes eventos, esquematicamente representados abaixo:

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

Formulários

A programação baseada em autômatos é amplamente usada em análises lexicais e sintáticas .

Além disso, pensar em termos de autômatos (ou seja, quebrar o processo de execução em etapas de autômato e passar informações de etapa em etapa através do estado de autômato explícito ) é necessário para a programação orientada a eventos como a única alternativa ao uso de processos paralelos ou threads .

As noções de estados e máquinas de estados são freqüentemente usadas no campo da especificação formal . Por exemplo, o desenvolvimento de arquitetura de software baseado em UML usa diagramas de estado para especificar o comportamento do programa. Além disso, vários protocolos de comunicação são frequentemente especificados usando a noção explícita de estado (por exemplo, RFC  793 ).

O pensamento em termos de autômatos (etapas e estados) também pode ser usado para descrever a semântica de algumas linguagens de programação . Por exemplo, a execução de um programa escrito na linguagem Refal é descrita como uma sequência de etapas de uma chamada máquina Refal abstrata; o estado da máquina é uma visão (uma expressão Refal arbitrária sem variáveis).

Continuações na linguagem Scheme requerem pensamento em termos de etapas e estados, embora Scheme em si não seja de forma alguma relacionado a autômatos (é recursivo). Para possibilitar que o recurso call / cc funcione, a implementação precisa ser capaz de capturar um estado completo do programa em execução, o que só é possível quando não há nenhuma parte implícita no estado. Esse estado capturado é exatamente chamado de continuação e pode ser considerado o estado de um autômato (relativamente complicado). A etapa do autômato é deduzir a próxima continuação da anterior, e o processo de execução é o ciclo dessas etapas.

Alexander Ollongren em seu livro explica o chamado método de Viena de descrição semântica de linguagens de programação, que é totalmente baseado em autômatos formais.

O sistema STAT [1] é um bom exemplo de uso da abordagem baseada em autômatos; este sistema, além de outros recursos, inclui uma linguagem embarcada chamada STATL que é puramente orientada para autômatos.

História

Técnicas baseadas em autômatos foram amplamente utilizadas em domínios onde existem algoritmos baseados na teoria de autômatos, como análises de linguagem formal.

Um dos primeiros artigos sobre isso é de Johnson et al., 1968.

Uma das primeiras menções da programação baseada em autômatos como uma técnica geral é encontrada no artigo de Peter Naur , 1963. O autor chama a técnica de abordagem da máquina de Turing , no entanto, nenhuma máquina de Turing real é fornecida no artigo; em vez disso, a técnica baseada em etapas e estados é descrita.

Comparação com programação imperativa e procedural

A noção de estado não é propriedade exclusiva da programação baseada em autômatos. De um modo geral, o estado (ou estado do programa ) aparece durante a execução de qualquer programa de computador , como uma combinação de todas as informações que podem ser alteradas durante a execução. Por exemplo, um estado de um programa imperativo tradicional consiste em

• valores de todas as variáveis ​​e as informações armazenadas na memória dinâmica;
• valores armazenados em registradores;
• conteúdo da pilha (incluindo valores de variáveis ​​locais e endereços de retorno);
• valor atual do ponteiro de instrução .

Eles podem ser divididos na parte explícita (como valores armazenados em variáveis) e na parte implícita (endereços de retorno e o ponteiro de instrução).

Dito isso, um programa baseado em autômato pode ser considerado como um caso especial de um programa imperativo, no qual parte implícita do estado é minimizada. O estado de todo o programa obtido nos dois momentos distintos de entrada na seção de código da etapa pode diferir apenas no estado do autômato. Isso simplifica a análise do programa.

Relação de programação orientada a objetos

Na teoria da programação orientada a objetos , diz-se que um objeto tem um estado interno e é capaz de receber mensagens , responder a elas, enviar mensagens para outros objetos e alterar seu estado interno durante o tratamento da mensagem. Em uma terminologia mais prática, chamar o método de um objeto é considerado o mesmo que enviar uma mensagem ao objeto .

Assim, por um lado, os objetos da programação orientada a objetos podem ser considerados autômatos (ou modelos de autômatos) cujo estado é a combinação de campos privados, e um ou mais métodos são considerados o passo . Tais métodos não devem chamar uns aos outros nem a si próprios, nem direta nem indiretamente, caso contrário, o objeto não pode ser considerado como implementado de forma baseada em autômato.

Por outro lado, objeto é bom para implementar um modelo de autômato. Quando a abordagem baseada em autômatos é usada em uma linguagem orientada a objetos, um modelo de autômato é geralmente implementado por uma classe, o estado é representado com campos privados da classe e a etapa é implementada como um método; tal método é geralmente o único método público não constante da classe (além de construtores e destruidores). Outros métodos públicos podem consultar o estado, mas não o alteram. Todos os métodos secundários (como manipuladores de estado específicos) geralmente estão ocultos na parte privada da classe.

Veja também

• Autômato celular
• Programação não determinística
• Padrão de estado
• Esterel , uma linguagem baseada em autômatos
• Umple , uma ferramenta para adicionar autômatos a Java e C ++

Referências

links externos

• JV Noble. «Finite State Machines in Forth» - programação baseada em autômatos em Forth
• Harel, David (1987). "Statecharts: A Visual Formalism for Complex Systems" (PDF) . Sci. Comput. Programação . 8 (3): 231–274. doi : 10.1016 / 0167-6423 (87) 90035-9 .
• Harel, David; Drusinsky, D. (1989). "Usando Statecharts para Descrição e Síntese de Hardware". Transações IEEE em Projeto Auxiliado por Computador de Circuitos Integrados e Sistemas . 8 (7): 798–807. doi : 10.1109 / 43.31537 . S2CID  8754800 .
• Polikarpova NI, Shalyto AA Automata-based programming SPb .: Piter. 2009 (rus)
• ITMO University, departamento de "Tecnologia de Programação"