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”.
right|autômaton's diagram 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 = { /* ' ' '\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; 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 = { /* ' ' '\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