Autômatos finitos 101
Autômatos finitos 101
Praticamente todo programa nasce pequeno e vai ganhando complexidade com o tempo. Um grande sintoma de desorganização ou "débito técnico" é a dificuldade crescente em controlar o estado do programa.
Imagine um programinha que, originalmente, imprime senhas, como naqueles quiosques que se encontram em bancos ou repartições de atendimento ao público. O controle é apenas um botão, e o programa só tem dois estados.
(botão)
Parado ---------------> Imprimindo
<---------------
(impressão terminada)
Por ser um programa tão simples, o controle do estado pode ser uma simples variável booleana "imprimindo".
Um belo dia, adicionam um penduricalho ao quiosque: um teclado. O usuário ganha a opção de digitar o número da senha para consultar sua posição na fila, tempo estimado de atendimento, etc. Para lidar com isso, adicionamos uma variável booleana "digitando" (não se pode imprimir senha enquanto digita), mais uma variável "mostrando".
Aí alguém digita um número e não pressiona ENTER. Os próximos usuários só sabiam apertar o botão original, e nada dele emitir senha. Em resposta, mais um penduricalho: um timer que restaura o estado "Parado" depois de alguns segundos sem digitação.
Mas o programador usou uma thread para implementar o timer e esqueceu de tratar o caso da consulta ser cancelada ou terminada rapidamente. O timer foi estourar na mão do próximo usuário, cuja senha foi impressa pela metade. Como threads não podem ser canceladas, e apenas testar a variável "digitando" não é suficiente, já que pode ser um outro usuário realizando outra consulta, nosso heroi adicionou mais uma variável: "timer_cancelado".
Outro problema: alguém pressionou uma tecla numérica enquanto o ticket era impresso. O evento de tecla mudava para modo digitação sem testar primeiro se "imprimindo" era verdadeiro. Mais um monte de if's aqui e ali para evitar esse caso fortuito.
Neste ponto, já temos quatro variáveis booleanas de estado, que em conjunto podem representar 16 estados possíveis, com 256 possíveis transições de um estado para o próximo. Porém, desse universo, apenas 4 estados e 8 transições são válidos:
Evento Transição ----------------------- ------------------------ Botão de senha Parado -> Imprimindo Impressão ok Imprimindo -> Parado Primeiro dígito Parado -> Digitando Próximos dígitos Digitando -> Digitando ENTER Digitando -> Mostrando Tecla ESC ou timer Digitando -> Parado ENTER ou botão de senha Mostrando -> Parado
O ato reflexo é encher o código de if's para evitar cair em estados "proibidos" (e.g. Imprimindo e Digitando ao mesmo tempo) e também para evitar transições proibidas (e.g. impressão interrompida quando pressiona alguma tecla). O código fica um espaguete, e qualquer adição de recurso é um pesadelo, pois o número de estados e transições vai aumentando exponencialmente.
Um passo na direção certa é substituir as "n" variáveis booleanas por apenas um número de estado. Se o desenvolvedor for caprichoso, usa uma enumeração. Os estados "proibidos" deixam de ser ameaça, porém ainda há um bom número de transições proibidas a descoberto. Cada tratador de evento (tecla, botão, impressora, timer) ainda tem alguns if's. O espaguete à carbonara virou espaguete ao sugo.
A solução é um dos mais velhos design patterns que existem: o autômato finito ou máquina de estado. Apesar da idade, é surpreendente a quantidade de código que a gente vê por aí, que não tira proveito dele. Talvez porque são ensinados de forma cientificista, como parte da cadeira de matemática discreta, junto com funções parciais, cardinalidade de conjuntos infinitos, P versus NP e outros bichos que um programador médio nunca usa no dia-a-dia da profissão.
Na história do início do texto, o ideal seria ter usado um autômato finito desde a primeira hora, quando só havia dois estados. E sim, eu também sou preguiçoso e também começo meus projetos do jeito errado, e só me resigno a fazer o grande refactoring quando as coisas começam a sair do controle, e a preguiça de testar torna-se maior que a preguiça de consertar.
Aqui seria o lugar de "vender o peixe", de explicar por que o autômato finito resolve ou pelo menos diminui os problemas citados acima. Porém fica mais fácil para mim ir mostrando isso ao longo do texto.
Pelo menos eu gosto de começar com caneta e papel. Geralmente a primeira tentativa fica meio feia, mas basta ir passando a limpo:
Para definir um autômato finito, precisamos definir a) os estados, b) as transições válidas entre estados, c) os eventos que provocam as transições, e d) que tarefa deve ser executada quando a transição acontece.
Cada um desenha isso do jeito que quiser; o que funciona para mim é colocar os estados como nós de um grafo, as transições como vértices e os eventos anotados perto de cada vértice.
Aqui aparece a primeira vantagem: a obrigação de pensar como o sistema funciona. Quando se trata de software que foi sendo desenvolvido sem modelo algum, só este exercício já torna evidente muitos bugs.
Em primeiro lugar, dever-se-ia procurar por um autômato já pronto, seja qual for a linguagem de programação, porque certamente ele já existe. Porém, é tão fácil fazer um que acabo quase sempre desenvolvendo do zero.
Vou usar a linguagem Swift como exemplo. Começo com uma matriz associativa e uma variável de estado. Uma lista com nomes humanamente legíveis para os estados também facilita na hora de debugar:
typealias SMTrans = (AnyObject?) -> Bool
enum SM: Int {
case inicio = 0
case parado
...
}
var SMnames = ["INICIO", ...]
var _state = SM.inicio
var sm: [SM:[SM:SMTrans]] = [:]
A função "trans" abaixo é chamada quando algum evento deseja mudar o estado.
func trans(_ newstate: SM, graceful: Bool, cargo: AnyObject?) -> Bool
{
let oldstate = self._state
if self.sm[oldstate] == nil || self.sm[oldstate]![newstate] == nil
if !graceful {
NSLog("########### transicao invalida %@ -> %@",
SMnames[oldstate.rawValue],
SMnames[newstate.rawValue])
}
return false
}
NSLog("Trans %@ -> %@",
SMnames[oldstate.rawValue],
SMnames[newstate.rawValue])
self._state = newstate
self.sm[oldstate]![newstate]!(cargo)
return true
}
Conforme se vê no código acima: se a transição é válida, o código associado à transição é executado. Se não, um erro é logado. (Mais adiante explico os parâmetros extras "graceful" e "cargo".)
Esta é outra vantagem do autômato finito: todos aqueles if's que estavam espalhados no código para evitar que uma transição proibida fosse cometida, podem ser removidos. Qualquer parte do programa pode tentar mudar o estado do autômato, mas ele só "aceita" a transição quando é válida. Claro que transições inválidas não devem ser tentadas, é sintoma de bug na rotina que tentou; é por isso que tais falhas devem ser logadas, e depois consertadas. Mas uma transição recusada é muito melhor do que deixar o programa fazer o que não devia.
Em seguida, adicionamos as transições de estado válidas (uma por vértice do grafo) e também o código que deve rodar quando elas acontecem.
sm[SM.inicio] = [:]
...
sm[SM.inicio]![SM.parado] = { _ in
ultima_senha = 1
... mais codigo executado ao iniciar ..
}
sm[SM.parado]![SM.imprimindo] = { _ in
imprimeSenha(ultima_senha)
ultima_senha += 1
}
sm[SM.imprimindo]![SM.parado] = { _ in
// não faz nada
}
Eu uso funções anônimas, closures ou Runnables (no Java) para conter o código. Alguns autômatos finitos prontos para uso permitem anexar "observadores" a cada transição, de modo que mais de um código seja executado quando ela acontece, mas eu prefiro que a tarefa da transição esteja completamente definida num único lugar.
Este seria o autômato suficiente para realizar a tarefa original do nosso quiosque, que era imprimir senhas. Para usá-lo, basta provocar as transições:
func inicio_do_programa()
{
trans(SM.parado, graceful: false, cargo: nil)
}
func botao_foi_pressionado() {
trans(SM.imprimindo, graceful: true, cargo: nil)
}
func impressora_terminou() {
trans(SM.parado, graceful: false, cargo: nil)
}
No caso do pressionamento de botão, passei o parâmetro "graceful" como verdadeiro porque é perfeitamente possível que algum usuário fique pressionando o botão enquanto a impressora ainda não terminou. A transição não deve acontecer, mas isto não deve ser logado como um erro, porque é uma falha esperada. Já as transições provocadas pela impressora e pelo início do programa, se tentarem provocar transições proibidas, devem sempre ser logadas.
Agora, passemos à parte da máquina de estado para consulta da senha. Em algumas transições, eu faço do valor "cargo" para transportar o número digitado pelo usuário:
sm[SM.parado]![SM.digitando] = { cargo in
let c = cargo as! String
if eh_digito(c) {
reinicia_timer()
numero_digitado = c
} else {
// volta
trans(SM.parado)
}
}
sm[SM.digitando]![SM.digitando] = { cargo in
let c = cargo as! String
if eh_digito(c) {
reinicia_timer()
numero_digitado += c
} else if eh_ENTER(c) {
trans(SM.mostra_consulta)
} else if eh_ESC(caracter) {
// desiste
trans(SM.parado)
}
}
sm[SM.digitando]![SM.mostra_consulta] = { _ in
reinicia_timer()
... exibe consulta na tela ...
}
sm[SM.digitando]![SM.parado] = { _ in
cancela_timer()
}
sm[SM.mostra_consulta]![SM.parado] = { _ in
... limpa tela ...
cancela_timer()
}
No tratador de teclado, eu passo a tecla através de trans(cargo:), o que nos poupa de mais uma variável global.
func tecla_foi_presionada(tecla: String)
{
if ! trans(SM.digitando, graceful: true,
cargo: tecla as AnyObject) {
trans(SM.parado, graceful: true, cargo: nil)
}
}
func timer_finalizado()
{
trans(SM.parado, graceful: true, cargo: nil)
}
(A propósito, o nome "cargo" é uma singela homenagem dos meus tempos de Clipper 5, que utilizava este nome para dados acessórios passados via callback. Também poderia ser entendido como "contrabando", pois lhe empresta uma capacidade que um autômato finito "puro" não tem.)
Na função acima, fiz uso de mais um truque. Como trans() retorna falso caso a transição seja inválida, eu uso isso como uma forma simples de optar etnre duas transições. Se a transição para "digitando" falhar, deve ser porque a máquina está exibindo uma consulta, e neste caso ela causa "digitando-parado".
Mas ainda há um bug e um risco no código acima.
Primeiro: se a máquina de estado estiver "imprimindo", a transição "imprimindo-parado" é válida, mas do jeito que está, pressionar uma tecla também causa esta mesma transição, interrompendo a impressora. (As transições não têm "dono".)
O remédio, na minha opinião: é criar um estado a mais: "imprimiu". Apenas a impressora provoca a transição "imprimindo-imprimiu". O código desta transição simplesmente faz "imprimiu-parado". O risco da tecla interromper a impressão foi eliminado, pois a antiga transição "imprime-parado" não existe mais.
Segundo: o tratamento do timer ainda está meio sujo. Se se esquecer de cancelar o timer em algum lugar, ele ainda pode causar problemas. Novamente, criar um estado a mais ("timeout") deixa tudo mais limpo, a ponto do timer nem precisar mais ser cancelado:
func timer_finalizado()
{
trans(SM.timeout, graceful: true, cargo: nil)
}
sm[SM.digitando]![SM.parado] = { _ in
// não faz nada
}
sm[SM.digitando]![SM.timeout] = { _ in
trans(SM.parado, graceful: false, cargo: nil)
}
sm[SM.timeout][SM.parado] = { _ in
// não faz nada
}
sm[SM.mostra_consulta]![SM.parado] = { _ in
... limpa tela ...
}
sm[SM.mostra_consulta]![SM.timeout] = { _ in
... limpa tela ...
trans(SM.parado, graceful: false, cargo: nil)
}
Um timer extemporâneo deixou de ser problema porque apenas as transicões "digitando-timeout" e "mostrando-timeout" são válidas. Em qualquer outro estado ("parado", "imprimindo", "imprimiu"), o timeout é ignorado. Se por acaso uma consulta for cancelada e uma nova consulta for iniciada, o timer ainda ativo não é um problema, porque a primeira coisa que a transição "parado-digitando" faz é reiniciar o timer.
Sim, quando se usa autômato finito é preciso adaptar o estilo do código para que ele encaixe no modelo. O grosso do seu código vai estar associado às transições de forma fragmentada; não vai mais ser executado "de cima para baixo". Como cada pedaço de código vai reagir a uma mudança de estado, que por sua vez vai ser causada por um evento, a estrutura do código lembra programação assíncrona, tipo Node.js, que muitos estranham e alguns nunca se acostumam.
O autômato finito também é um modelo bastante limitado, o que por exemplo nos obrigou a criar estados intermediários para tratar timeout e impressão de forma segura.
Não raro o autômato finito começa a ficar muito complexo, com muitos estados e muitíssimas transições possíveis, e o espaguete está de volta. Uma solução é adotar múltiplos autômatos finitos, com ou sem relação hierárquica entre eles. Por exemplo, no caso do quiosque poderíamos ter três autômatos, um principal e dois acessórios:
Na proposta acima, os dois autômatos subordinados possuem um estado terminal, em que eles "morrem", devolvendo o controle ao autômato-mestre. Aqueles estados "imprimiu" e "timeout" não foram mais necessários.
Para o autômato finito, o mundo ideal é: um evento, uma transição, nem mais nem menos. É difícil modelar transições que dependam de múltiplas condições independentes. Por exemplo, uma bomba que exija o pressionamento de três botões (A, B, C) em qualquer ordem, sem repetição. Modelá-la como um autômato finito fica bem confuso:
No caso do "meu" autômato finito, a variável "cargo" poderia ser usada como memória das teclas já pressionadas. Mas o fato é que não ficou legal. A rede de Petri seria a ferramenta correta aqui.
Parte da atratividade de ferramentas novas como React e Vue.js é derivada das vantagens da máquina de estados, em particular quando se faz uso dos respectivos gerenciadores de estado da aplicação, Redux e Vuex.
Das máquinas de estado teóricas, o autômato finito é o mais "burro". A única "memória" dele é o próprio estado. Muitos sistemas são complexos demais para ele. A Rede de Petri é um tipo mais poderoso, bastante popular entre estudiosos de protocolos de rede. O autômato mais poderoso é a Máquina de Turing, a que equivale todo computador de uso geral.
Uma expressão regular pode ser convertida em autômato finito e vice-versa. As limitações de um também se aplicam ao outro. Por exemplo, é quase impossível testar (com precisão) se um e-mail é válido usando apenas uma expressão regular, e é igualmente inadequado tentar fazê-lo com um autômato finito.
Uma outra grande utilidade de especificar uma máquina de estado usando autômato finito ou rede de Petri é a verificação mecânica: e.g. detectar estados e/ou transições que nunca são usados, que cheiram a bug.