Programação orientada a autômatos

Programação orientada a autômatos é um paradigma de programação no qual o programa (ou partes dele) é pensado como um modelo de uma máquina de estados finitos (FSM, do inglês, finite state machine) ou qualquer outro (geralmente mais complicado) autômato formal (ver teoria de autômatos). Algumas vezes um conjunto potencialmente infinito de possíveis estados é introduzido, e tal conjunto pode ter uma estrutura complicada, não sendo apenas uma enumeração.

A programação orientada a máquinas de estados finitos é geralmente semelhante mas, formalmente falando, não cobre todas as possíveis variantes que uma FSM representa, e a programação orientada a autômatos não necessariamente emprega FSM de forma estrita.

As propriedades seguintes são indicadores chaves de uma programação orientada à autômatos:

O período de tempo da execução do programa é claramente separado em passos do autômato. Cada um dos passos é a efetiva execução de uma seção de código (igual para todos os passos), no qual existe um único ponto de entrada. Tal seção pode ser uma função ou uma rotina, ou apenas um corpo cíclico. A etapa da seção pode ser dividida em subseções para serem executadas a depender dos diferentes estados, ainda que isto não seja necessário.
Qualquer comunicação entre os passos só é possível mediante um conjunto explicitamente conhecido de variáveis nomeadas estado. Entre dois passos, o programa (ou suas partes criadas usando a técnica baseada em autômatos) pode não ter componentes implícitos de seu estado, tal como valores de (pilha) variáveis locais, endereços de retorno, ponteiro de instrução atual etc. Isto é, dados quaisquer dois momentos de iniciação do passo do autômato, eles diferem apenas nos valores das variáveis, sendo considerados como o estado do autômato.

A completa execução do código orientado a autômatos é um ciclo (possivelmente explícito) de passos de um autômato.

Outra razão para usar a noção de programação orientada a autômatos é que o estilo de raciocínio do programador, nessa técnica, é muito similar ao estilo de raciocínio usado para resolver problemas relacionados matemáticos usando máquina de Turing, algoritmo de Markov etc.

Exemplo

Considere um programa em C que lê um texto de um standard input stream, linha por linha, e imprime a primeira palavra de cada linha. É claro que precisamos primeiro ler e pular os espaços do início, se houver; depois, ler os caracteres da primeira palavra e imprimi-los até a palavra terminar, e finalmente ler e ignorar todos os caracteres restantes até que o caractere especial de fim-de-linha seja encontrado. Uma vez encontrado (independentemente do estágio), reiniciamos o algoritmo e, uma vez encontrada a condição de “fim-de-arquivo” (independentemente do estágio), terminamos o programa.

Programa em C (imperativo) Tradicional

O programa que soluciona a tarefa do exemplo, no estilo tradicional, assemelha-se ao seguinte:

#include <stdio.h>
int main(void)
{
    int c;
    do {
        c = getchar();
        while(c == ' ')
            c = getchar();
        while(c != EOF && c != ' ' && c != '\n') {
            putchar(c);
            c = getchar();
        }
        putchar('\n');
        while(c != EOF && c != '\n')
            c = getchar();
    } while(c != EOF);
    return 0;
}

Programa orientado a autômatos

A mesma tarefa pode ser resolvida seguindo-se o raciocínio empregado em termos de máquinas de estados finitos. Observa-se que o processamento da linha tem 3 estágios:

Ignorar os espaços em branco
Imprimir a palavra
Ignorar o restante dos caracteres.

Vamos chamá-los estados before, inside and after. O programa se assemelhará a isto:

#include <stdio.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        switch(state) {
            case before:
                if(c == '\n') {
                    putchar('\n');
                } else
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                switch(c) {
                    case ' ':  state = after; break;
                    case '\n':
                        putchar('\n');
                        state = before;
                        break;
                    default:   putchar(c);
                }
                break;
            case after:
                if(c == '\n') {
                    putchar('\n');
                    state = before;
                }
        }
    }
    return 0;
}

Embora o código agora pareça mais longo, ao menos ele tem uma vantagem significativa: há apenas uma instrução de leitura (isto é, uma chamada à função getchar()) no programa. Além disso, existe apenas um loop em vez dos quatro que a versão prévia possuía.

Neste programa, o corpo do loop while é o passo do autômato , e o proprio loop é o “ciclo de trabalho do autômato”.

O Programa implementa (modela) o trabalho de uma “máquina de estados finita” mostrada na imagem. O N denota o caractere de fim-de-linha, o S denota os espaços e A representa todos os outros caracteres. O autômato segue exatamente uma seta em cada etapa, dependendo do estado atual e do caractere encontrado. Alguns detectores de estado são acompanhados com a impressão de um caractere, tais setas são marcadas com asteriscos.

Não é necessário dividir o código em tratadores separados para cada estado original. Além disso, em alguns casos, o próprio conceito do “estado” pode ser composto por vários valores de variáveis, de modo que pode ser impossível lidar com cada estado possível explicitamente. No programa discutido, é possível reduzir o comprimento do código notando que as medidas tomadas em resposta ao sinal de fim-de-linha são os mesmos para todos os estados possíveis. O seguinte programa é igual ao anterior, mas é um pouco mais curto:

#include <stdio.h>
int main(void)
{
    enum states {
        before, inside, after
    } state;
    int c;
    state = before;
    while((c = getchar()) != EOF) {
        if(c == '\n') {
            putchar('\n');
            state = before;
        } else
        switch(state) {
            case before:
                if(c != ' ') {
                    putchar(c);
                    state = inside;
                }
                break;
            case inside:
                if(c == ' ') {
                    state = after;
                } else {
                    putchar(c);
                }
                break;
            case after:
                break;
        }
    }
    return 0;
}

A função separada para a etapa de automação

A propriedade mais importante do programa anterior é que a seção de passo do código autômato é claramente localizada. Com uma função separada para isso, podemos melhor demonstrar essa propriedade:

#include <stdio.h>
enum states { before, inside, after };
void step(enum states *state, int c)
{
    if(c == '\n') {
        putchar('\n');
        *state = before;
    } else
    switch(*state) {
        case before:
            if(c != ' ') {
                putchar(c);
                *state = inside;
            }
            break;
        case inside:
            if(c == ' ') {
                *state = after;
            } else {
                putchar(c);
            }
            break;
        case after:
            break;
    }
}
int main(void)
{
    int c;
    enum states state = before;
    while((c = getchar()) != EOF) {
        step(&state, c);
    }
    return 0;
}

Este exemplo demonstra claramente as propriedades básicas do código baseado em autômatos:

Períodos de tempo da etapa de execuções do autômato não podem se sobrepor
A única informação transmitida a partir do passo anterior para a próxima é o estado do autómato explicitamente especificado

Tabela de transição de estado explícita

Um autômato finito pode ser definido por uma Tabela de transição de estados explícita. De um modo geral, um código de programa baseado em autômatos pode naturalmente refletir esta abordagem. No programa abaixo, há uma matriz chamada the_table, que define a tabela. As linhas da tabela representam três “estados”, enquanto colunas refletem os caracteres de entrada (o primeiro para espaços, o segundo para o caractere de fim-de-linha, e o último é para todos os outros caracteres).

Para cada combinação possível, a tabela contém o número do novo Estado e uma bandeira, que determina se o autômato deve imprimir o símbolo. Em uma tarefa na vida real, isso pode ser mais complicado, por exemplo, a tabela poderia conter ponteiros para funções a serem chamadas em todas as combinações possíveis de condições.

#include <stdio.h>
enum states { before = 0, inside = 1, after = 2 };
struct branch {
    unsigned char new_state:2;
    unsigned char should_putchar:1;
};
struct branch the_table[3][3] = {
                 /* ' '         '\n'        others */
    /* before */ { {before,0}, {before,1}, {inside,1} },
    /* inside */ { {after, 0}, {before,1}, {inside,1} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
void step(enum states *state, int c)
{
    int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
    struct branch *b = & the_table[*state][idx2];
    *state = (enum states)(b->new_state);
    if(b->should_putchar) putchar(c);
}

Automação e autômatos

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

Um ciclo de produção é geralmente modelada como:

A seqüência de estágios progredindo de acordo com dados de entrada (a partir de captores).
Um conjunto de ações executadas, dependendo do estágio atual.

Várias linguagens de programação dedicadas permitem expressar tal modelo de uma maneira consideravelmente sofisticada.

Programa Exemplo

O exemplo apresentado acima pode ser expressa de acordo com este ponto de vista, como no seguinte programa. Aqui pseudo-código usa-se tais convenções:

'set' and 'reset', ativar e inativar uma variável lógica (aqui um estágio), respectivamente.
':' é atribuição, '=' é teste de igualdade.

SPC : ' '
EOL : '\n'

states : (before, inside, after, end)

setState(c) {
    if c=EOF then set end
    if before and (c!=SPC and c!=EOL) then set inside
    if inside and (c=SPC or c=EOL) then set after
    if after and c=EOL then set before
}

doAction(c) {
    if inside then write(c)
    else if c=EOL then write(c)
}

cycle {
    set before
    loop {
        c : readCharacter
        setState(c)
        doAction(c)
    }
    until end
}

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

Automação & Eventos

Na área de automação, progredir passo a passo depende de entrada de dados provenientes da própria máquina. Isto é representado no programa pela leitura de caracteres a partir de um texto. Na realidade, os dados informam sobre a posição, velocidade, temperatura, etc, dos elementos críticos de uma máquina. Como em programação de GUI, "mudanças" no estado da máquina podem, portanto, ser considerados como eventos que causam a passagem de um estado para outro, até que o final seja alcançado. A combinação dos estados possíveis pode gerar uma grande variedade de eventos, definindo assim um ciclo de produção mais complexo. Como consequência, os ciclos estão geralmente muito longe de serem sequências lineares simples. Há comumente ramos paralelos correndo juntos e alternativas sao selecionadas de acordo com diferentes eventos, representado esquematicamente abaixo:

   s:stage   c:condition

   s1
   |
   |-c2
   |
   s2
   |
   ----------
   |        |
   |-c31    |-c32
   |        |
  s31       s32
   |        |
   |-c41    |-c42
   |        |
   ----------
   |
   s4

Utilizando as capacidades orientadas a objeto

Se a linguagem de implementação suporta programação orientada a objeto, uma refatoração simples é encapsular o autômato em um objeto, ocultando assim os seus detalhes de implementação. Por exemplo, uma versão orientada a objectos em C + + do mesmo programa está abaixo. Uma refatoração mais sofisticada poderia empregar o State_pattern.

#include <stdio.h>
class StateMachine {
    enum states { before = 0, inside = 1, after = 2 } state;
    struct branch {
        enum states new_state:2;
        int should_putchar:1;
    };
    static struct branch the_table[3][3];
public:
    StateMachine() : state(before) {}
    void FeedChar(int c) {
        int idx2 = (c == ' ') ? 0 : (c == '\n') ? 1 : 2;
        struct branch *b = & the_table[state][idx2];
        state = b->new_state;
        if(b->should_putchar) putchar(c);
    }
};
struct StateMachine::branch StateMachine::the_table[3][3] = {
                 /* ' '         '\n'        others */
    /* before */ { {before,0}, {before,1}, {inside,1} },
    /* inside */ { {after, 0}, {before,1}, {inside,1} },
    /* after  */ { {after, 0}, {before,1}, {after, 0} }
};
int main(void)
{
    int c;
    StateMachine machine;
    while((c = getchar()) != EOF)
        machine.FeedChar(c);
    return 0;
}

Nota: Para minimizar as alterações não diretamente relacionadas com o tema do artigo, a entrada / saída de funções da biblioteca padrão de C estão sendo usadas. Note a utilização do operador ternário, que também pode ser implementada como if-else.

Aplicações

Programação baseada em autômatos é amplamente utilizado na lexical e análises sintáticas.^[1]

Além disso, pensando em termos de autômatos (isto é, quebrando o processo de execução até “passos de autômato” e passar informações passo a passo através do Estado explícito) é necessária para programação orientada a eventos como a única alternativa ao uso de processos ou threads paralelas.

As noções de estados e máquinas de estado são usadas frequentemente no campo de especificação formal. Por exemplo, UML-baseado em desenvolvimento de arquitetura de software utiliza diagramas de estado para especificar o comportamento do programa. Também vários protocolos de comunicação são muitas vezes especificados usando a noção explícita de Estado (ver, por exemplo, RFC 793^[2]). Pensar em termos de autômatos (etapas e estados) também pode ser util para descrever a semântica de algumas linguagens de programação. Por exemplo, a execução de um programa escrito em linguagem Refal é descrito como uma sequência de “passos” de uma máquina Refal abstrata; o estado da máquina é uma “vista”' (uma expressão Refal arbitrária, sem variáveis).

Continuação em linguagem  Scheme requer raciocínio em termos de etapas e estados, embora Scheme em si não é de forma alguma relacionado a autômatos (é recursivo). Para tornar possível que o recurso call / cc  funcione, a sua aplicação deve ser capaz de pegar um estado inteiro do programa em execução, o que só é possível quando não há nenhuma parte implícita no estado. Tal “estado capturado” é justamente a coisa denominada “continuação”, e pode ser considerado como o “estado” de um (relativamente complicado) autómato. O passo do autómato  é  deduzir a seguinte continuação do anterior, e o processo de execução é o ciclo de tais passos.

Alexander Ollongren em seu livro^[3] Explica o chamado “método Vienna” de descrição de semânticas de linguagens de programação que é completamente baseado em autômatos formais O sistema STAT ~ seclab / projects / stat / index.html é um bom exemplo de como usar a abordagem baseada em autômatos; este sistema, além de outros recursos, inclui uma linguagem embutida chamada “STATL” que é puramente orientada a autômatos.

História

Técnicas baseadas em autômatos foram amplamente utilizadas nos domínios onde há algoritmos baseados na teoria de autômatos, tais como análises linguagem formais.^[1]

One of the early papers on this is by Johnson et al., 1968.^[4] Uma das primeiras menções a programação baseada em autômatos como uma técnica geral o é encontrado no artigo de Peter Naur, 1963.^[5] O autor chama a técnica de “Abordagem máquina de Turing”, contudo não existe realmente uma máquina de Turing no artigo; Ao invés, a técnica baseada em estados e passos é descrita.

Comparando à programação imperativa e procedural

A noção de estado não é propriedade exclusiva da programação baseada em autômatos. ^[6] De modo geral, 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 pode mudar durante a execução. Por exemplo, um “estado” de um programa imperativo tradicional consiste de:

Valores de todas as variáveis e as informações armazenadas na memória dinâmica
Os valores armazenados nos registros
Conteúdo da pilha (incluindo os valores das variáveis locais e endereços de retorno)
Valor atual do ponteiro de instrução

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

Dito isto, um programa baseado em autômatos pode ser considerado como um caso especial de um programa imperativo, no qual a parte implícita do estado é minimizado. O estado de todo o programa, tomados nos dois momentos distintos de entrada em uma seção de passo do código' podem diferir apenas no estado de autômato. Isto simplifica a análise do programa.

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

Na teoria da programação orientada a objetos um objeto é dito ter umestado interno e é capaz de receber “mensagens”,e responder a elas, enviando mensagens para outros objetos e alterando o estado interno durante o manuseio mensagem. Na terminologia mais prática, “chamar de um método de objeto é considerado o mesmo que enviar uma mensagem para o objeto.

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

Por outro lado, é óbvio que o objeto é bom para a implementação de um modelo de um autômato. Quando a abordagem baseada em autômatos é usado dentro de uma linguagem orientada a objetos, um modelo de autômato é geralmente implementado por uma classe, o Estado está representado com os campos internos (privados) da classe, bem como o “passo” é implementado 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 mudá-lo. Todos os métodos secundários (como manipuladores particulares do estado) são normalmente escondido dentro da parte privada da classe.

Veja também

Nondeterministic programming
State pattern
Esterel, an automata-based language

Referências

↑ ^a ^b Aho, Alfred V.; Ullman, Jeffrey D. (1973). The theory of parsing, translation and compiling. 1. Englewood Cliffs, N. J.: Prentice-Hall. ISBN 0-13-914564-8
↑ RFC 793
↑ Ollongren, Alexander (1974). Definition of programming languages by interpreting automata. London: Academic Press. ISBN 0-12-525750-3
↑ Johnson, W. L.; Porter, J. H.; Ackley, S. I.; Ross, D. T. (1968). «Automatic generation of efficient lexical processors using finite state techniques». Comm ACM. 11 (12): 805–813. doi:10.1145/364175.364185
↑ Naur, Peter (setembro de 1963). «The design of the GIER ALGOL compiler Part II». BIT Numerical Mathematics. 3 (3): 145–166. doi:10.1007/BF01939983
↑ 2008. http://books.ifmo.ru/NTV/NTV_53.pdf (rus). «Automata-based programming». Bulletin of St Petersburg State University of Information Technologies, Mechanics and Optics. 53

Ligações externas

J. V. Noble. «Finite State Machines in Forth» — automata-based programming in Forth
Harel, David (1987). «Statecharts: A Visual Formalism for Complex Systems» (PDF). Sci. Comput. Programming. 8 (8): 231–274. doi:10.1016/0167-6423(87)90035-9
Harel, David; Drusinsky, D. (1989). «Using Statecharts for Hardware Description and Synthesis». IEEE Trans. Computer Aided Design of Integrated Circuits and Systems (8): 798–807
Polikarpova N. I., Shalyto A. A. Automata-based programming SPb.: Piter. 2009 (rus)

[gram-1] Aho, Alfred V.; Ullman, Jeffrey D. (1973). The theory of parsing, translation and compiling. 1. Englewood Cliffs, N. J.: Prentice-Hall. ISBN 0-13-914564-8

[2] RFC 793

[3] Ollongren, Alexander (1974). Definition of programming languages by interpreting automata. London: Academic Press. ISBN 0-12-525750-3

[4] Johnson, W. L.; Porter, J. H.; Ackley, S. I.; Ross, D. T. (1968). «Automatic generation of efficient lexical processors using finite state techniques». Comm ACM. 11 (12): 805–813. doi:10.1145/364175.364185

[5] Naur, Peter (setembro de 1963). «The design of the GIER ALGOL compiler Part II». BIT Numerical Mathematics. 3 (3): 145–166. doi:10.1007/BF01939983

[6] 2008. http://books.ifmo.ru/NTV/NTV_53.pdf (rus). «Automata-based programming». Bulletin of St Petersburg State University of Information Technologies, Mechanics and Optics. 53

[1]

[2]

[3]

[4]

[5]

[6]