De un grafo a una máquina de estados

Casi todo el mundo ha implementado una máquina de estados sin llamarla así. El ciclo de vida de un pedido, el de una descarga, el de una conexión. Muchas veces se modela con un puñado de booleanos sueltos que, tres meses después, nadie sabe leer. Para eso existen las máquinas de estados.

Antes de llegar ahí conviene construir el concepto desde abajo. Y abajo del todo hay un grafo.

01 — El grafo

Un autómata es un grafo con reglas encima, así que hay que empezar por el grafo.

Un grafo es la estructura más simple para representar relaciones. Dos conjuntos: nodos (los elementos) y aristas (las conexiones entre ellos).

Las estaciones de metro son un grafo: cada estación es un nodo, cada tramo de vía que une dos estaciones es una arista. Una red de amigos también: las personas son nodos, las amistades son aristas.

Formalmente se escribe G = (V, E): V es el conjunto de vértices (nodos) y E el de aristas (edges). No hace falta más para empezar.

02 — El grafo dirigido

En el grafo del metro, una arista no tiene dirección. Si la línea une Sol con Gran Vía, une Gran Vía con Sol. La conexión es simétrica.

En un grafo dirigido (directed graph o digraph) las aristas tienen sentido. La arista va de A a B, y eso no implica que exista de B a A.

Seguir a alguien en una red social es un grafo dirigido: que una cuenta siga a otra no significa que la otra la siga de vuelta. Una calle de sentido único, lo mismo.

Esa asimetría es lo que permite modelar “desde aquí puedes ir allí, pero no al revés”.

03 — El autómata: un grafo con reglas

Un autómata finito es un grafo dirigido al que se le añaden cuatro reglas:

• Los nodos dejan de ser “elementos” y pasan a ser estados.
• Las aristas dejan de ser conexiones sueltas y pasan a ser transiciones, cada una etiquetada con el evento que la dispara.
• Un estado es el inicial: por dónde se empieza.
• Uno o varios son finales o de aceptación.

Un semáforo es un autómata finito que todos llevamos en la cabeza. Tres estados: Verde, Ámbar y Rojo. El evento que dispara el cambio es el paso del tiempo, y las transiciones van en un único sentido: Verde → Ámbar → Rojo → Verde, y vuelta a empezar. De Verde no se salta a Rojo: esa arista no existe en el grafo, y por eso no ocurre. El Ámbar está ahí precisamente para que ese salto sea imposible.

Formalmente un autómata finito se define como (Q, Σ, δ, q0, F): el conjunto de estados, el alfabeto de eventos posibles, la función de transición, el estado inicial y los finales. De toda esa notación hay que quedarse con una sola idea: un autómata finito no tiene más memoria que el estado en el que está. Todo lo que “sabe” es dónde está ahora.

04 — El límite finito

Ese límite (no tener más memoria que el estado actual) es lo que separa lo finito de lo infinito. El conjunto de estados es finito. Cuando hace falta recordar una cantidad de información que no está acotada, un número finito de estados no basta, y hay que subir de nivel: un autómata de pila añade una pila como memoria, y una máquina de Turing añade una cinta infinita. El infinito nunca está en el dibujo del grafo — está en la memoria.

En programación casi nunca se quiere llegar ahí. Si el número de estados empieza a crecer sin control o depende de los datos, mala señal: el modelo está mal planteado, y añadir estados solo lo esconde.

Un número de estados que explota suele ser síntoma de que hay una variable disfrazada de estado.

05 — La máquina de estados

Una máquina de estados finitos (FSM) es ese grafo dirigido llevado al código: un número finito de estados, el sistema está en uno solo a la vez, y pasa a otro únicamente cuando ocurre un evento que dibuja esa transición. Nada más puede pasar.

El ejemplo canónico es un gestor de descargas:

Máquina de estados · gestor de descargas

estado inicialestado terminal

• Pendiente: la descarga existe pero no ha arrancado.
• Descargando: en curso. Puede pausarse o cancelarse.
• Pausada: detenida. Reanudarla vuelve a Descargando (ese retorno es un ciclo, y es perfectamente legal) o puede cancelarse.
• Completada, Fallida y Cancelada: estados terminales, sin aristas de salida. Es fin de trayecto, no exactamente los “finales” de un autómata (que pueden seguir teniendo transiciones).

Fallida y Cancelada terminan el flujo igual, pero no son el mismo estado. Una la provoca el sistema; la otra la decide el usuario. Fundirlas en un único estado terminal ahorraría un estado y perdería justo el dato que importa cuando algo sale del camino feliz.

Lo interesante no es lo que se permite, sino lo que queda prohibido por construcción. No se puede pausar algo que está Pendiente: aún no ha empezado. Una descarga Pausada no puede fallar: no está transfiriendo nada, primero tendría que volver a Descargando. No se puede cancelar una descarga ya Completada. Esas transiciones no existen en el grafo, así que en el código tampoco deberían existir.

06 — El trade-off

Modelar un flujo como máquina de estados es un trade-off: añade estructura, y la estructura tiene un coste. Conviene ver los dos lados.

Lo que se gana. Frente a un puñado de booleanos, una FSM aporta cuatro cosas:

• Claridad. El flujo de control es explícito. Un estado a la vez. Desaparece el if (isPending && !isFailed && !isCompleted && isPaused) que nadie se atreve a tocar.
• Extensibilidad. Añadir un estado nuevo es añadir un nodo y sus aristas. Si la máquina está bien encapsulada, no se toca la lógica que ya funcionaba.
• Testeo. Cada transición es una unidad. Se testea “desde Pausada, el evento resume lleva a Descargando” por un lado, y “desde Completada, el evento resume no hace nada” por otro. Estado a estado, transición a transición.
• Mantenimiento. Cuando el estado es explícito, un bug de tipo “la descarga se quedó a medias en un limbo raro” deja de ser posible: o estás en un estado válido, o la transición falló de forma controlada.

Una FSM no simplifica el problema: lo hace explícito. Y un problema explícito se puede testear, extender y depurar.

Lo que se paga, y cuándo no compensa. Esa estructura no todo flujo la merece. Si el proceso es trivialmente lineal — A → B → C, sin bifurcaciones, sin ciclos, sin ninguna transición inválida que sea peligrosa dejar pasar — montar una máquina de estados es sobreingeniería. Un par de campos y un método bastan.

La FSM merece la pena cuando hay transiciones que deben ser imposibles, cuando el mismo estado se consulta y se muta desde varios sitios, o cuando los booleanos empiezan a multiplicarse y a contradecirse entre ellos: isPaused a true con isCompleted también a true es un estado que no debería existir, y que un único estado explícito no puede ni representar.

Por cierto: esta es la misma máquina que apareció en el post de Kafka, cuando dijimos que el productor tiene que validar el ciclo de vida de una booking antes de emitir eventos. Con otros nombres en los nodos, es el mismo dibujo.