Extendiendo el formalismo de máquinas de estados - I

Cuando modelamos el comportamiento de un sistema mediante máquinas de estados no siempre todo es bonito, claro y sencillo, en ciertas ocasiones debemos tomar diversas estrategías para resolver los pocos obstáculos que presenta el formalismo convencional de máquinas de estados.

A continuación resumo algunas de las problemáticas que he enfrentado al diseñar sistemas utilizando máquinas de estados, exponiendo el problema y luego presentando una o varias soluciones posibles extendiendo el formalismo convencional por medio de Statecharts.

Explosión de estados y transiciones

Este es sin dudas el mayor problema cuando el sistema que deseamos modelar es verdaderamente complejo. Para ejemplificar la situación supongamos que el diagrama de la figura modela inicialmente el sistema de interés.

Por alguna razón se requiere descomponer el estado A en dos nuevos estados C y D, es decir, cuando el sistema se encuentre en C o D, también lo estará en A.

Luego de un tiempo, las especificaciones requiren descomponer el estado B en tres nuevos estados H, I y K, por lo tanto, se procede de forma similar al caso anterior.

Un nuevo requerimiento descompone el estado D en dos nuevos estados E y F. A su vez, se requiere que el estado K se comporte de igual manera que D.

Para complicar aún más las cosas, agregamos el estado J a D y por lo tanto a K.

Aclaremos, que si bien los estados A, B, D y K no están explícitos dentro del diagrama, lo están implícitamente.

Ahora, utilizamos Statecharts para modelar el mismo sistema.

donde:

• A, D, B, K: son estados compuestos o superestados.
• C, E, J, F, H, I: son estados básicos o subestados.
• α,  β, γ, ε, θ: son eventos de entrada.

Del diagrama podemos realizar las siguientes observaciones:

• disminuyeron la cantidad de transiciones entre estados,
• los estados desagregados están explícitios,
• los estados permanecen anidados jerárquicamente,
• los estados compuestos manifiestan el concepto de modularidad,
• la descripción del comportamiento es clara y directa,
• permite redefinir el comportamiento de la máquina frente a sus eventos de entrada.

Esta última observación se manifiesta en el estado E dentro del superestado D, ya que E redefine el comportamiento frente al evento ε, es decir, si la máquina se encuentra en el estado E, dentro de D, y recibe el evento ε ejecuta la acción act3 que es diferente al comportamiento cuando la máquina se encuentra en el estado J o F, dentro de D, en este caso ejecuta la acción act4. Esto es una útil herramienta a la hora de utilizar Statecharts en sistema complejos.

Sin duda alguna, el formalismo visual introducido por Statecharts es sumamente poderoso, permitiendo diseñar y desarrollar sistemas más y más complejos, manteniendo la flexibilidad, modularidad y claridad en los modelos.
 

Es importante aclarar que el mayor aporte de Statecharts al formalismo tradicional es el anidamiento jerárquico de estados. Su objetivo radica en impedir las repeticiones, como lo que ocurre en los estados K y D, las cuales son inevitables en el formalismo convencional de máquinas de estados "planas". La semántica del anidamiento permite a los subestados definir únicamente las diferencias de comportamiento con sus superestados, y así permitiendo compartir y reutilizar el comportamiento. La relación entre un subestado y su superestado se denomina herencia del comportamiento.
 

Transiciones condicionadas

Supongamos que necesitamos modelar la siguiente situación mediante una máquina de estados:

Estando en el estado A si se recibe el evento α debe transitar hacia el estado B ejecutando la acción act1 si y sólo si la condición C1 es verdadera.

Claramente esta situación no puede resolverse simplemente con el formalismo tradicional.
Una de las posibles soluciones es adicionar memoria a la máquina de estados. Esta mantiene la información necesaria para determinar, en todo momento, la condición C1. Esto se logra incorporando el concepto de condiciones de guarda (guard conditions) o simplemente guardas, ofrecido en el formalismo Statecharts.

Las guardas son simplemente expresiones booleanas evaluadas dinámicamente, durante una potencial transición, en base a la información que almacena la memoria adicional, también denominada variables de estado extendedidas, para diferenciarla de la memoria principal de las máquinas, sus estados. Usadas con sumo cuidado las variables de estado extendidas y las guardas constituyen un mecanismo muy poderoso que simplifica drásticamente los diseños. Sin embargo, su uso excesivo convierte los diseños en lo que llaman spaghetti code el cual se elimina al utilizar las máquinas de estados.

Nuevamente, las guardas introducen las sentencias IF ELSE al formalismo convencional. Estas emergen de las transiciones y se concentran en los denominados pseudoestados o conectores condicionales, también conocidos como conditional branches.

Longitud del alfabeto de entrada

En ciertas ocasiones, cuando la máquina de estados acepta gran cantidad de eventos de entrada, estos pueden generan un número inmanejable de transiciones las cuales disminuyen la legibilidad del diagrama y aumentan su complejidad, conviertiéndolo, en ciertos casos, en un diagrama inmantenible. Para ser más explícito, supongamos que el conjunto de eventos de entrada está compuesto por los caracteres: 0-9/A-F. Increíblemente estos 16 eventos pueden ofuscar un simple diagrama, como se muestra a continuación.

Ahora, si agrupamos los eventos del mismo tipo, disminuimos la longitud del alfabeto y como consecuencia la cantidad de transiciones. Para este caso creamos dos grupos, DECIMAL que representa los eventos 0-9 y ALPHA los eventos A-F. A su vez estos grupos definen los eventos DECIMAL y ALPHA.


 Hasta aquí nada nuevo, sin embargo, si por algún motivo, la acción act1 requiere el caracter que provocó la transición, nuevamente necesitamos extender el formalismo, para incorporar el concepto de eventos con parámetros. Así, el evento DECIMAL tiene como parámetros: 0-9 y el evento ALPHA A-F. Entonces podríamos decir que los parámetros son la parte cuantitativa de los eventos.

Otro ejemplo es el de recibir números binarios en el rango de 0-255 en la capa de enlace de datos del lado receptor de un simple protocolo. Obviamente, es poco práctico manejar los 256 eventos de forma convencional, ya que generarían 256 transiciones de estados, por lo tanto, simplemente los agrupamos, definiendo el evento DATA, el cual tiene como parámetro uno de los 256 números binarios.

Bucles

Los bucles son otro de los contratiempos que enfrentamos al utilizar máquinas de estados, sin embargo podemos utilizar el concepto de guarda y variables de estado extendidas para incorporar la parte cuantitativa de un estado.
Supongamos que estamos diseñando el lado receptor de una sencilla capa de enlace de datos, en nuestro ejemplo la trama del protocolo especifica el tamaño del campo de datos, y como consecuencia, una vez recibido se esperan los datos del payload mediante un bucle tradicional, como muestra la siguiente figura. Aquí la memoria adicional es el contador de datos recibidos, como se muestra en el siguiente fragmento.

Recordando estados

Otra situación típica es la necesidad de recordar el pasado de la máquina de estados (al menos los estados por lo cuales la máquina transitó anteriormente). Para mostrar dicha situación, representemos la siguiente premisa:

...cuando el sistema se encuentra en alguno de los estado A o B y recibe el evento α debe ejecutar el proceso definido por el bloque P. Adicionalmente, si desde este se recibe el evento β el sistema abandona P y transita hacia el estado desde el cual ingresó a P.

El comportamiento del proceso P se representa mediante una máquina de estados.

Modelamos utilizando el formalismo convencional.

Como vemos, debemos repetir todos los estados del proceso P y sus transiciones con el motivo de recordar el estado del sistema inmediatamente antes de ejecutar el proceso P.

Ahora, haremos lo mismo pero esta vez utilizando el concepto de reutilización o herencia del comportamiento, nuevamente Statecharts. Primeramente, declaramos el proceso P como el estado P, cuyos subestados son C, D y E, aplicando jerarquía de estados.

Luego resta introducir la manera en la cual "recordar el pasado", en Statecharts podemos resolverlo mediante la historia. Por historia nos referimos a determinar el estado pasado en un mismo nivel de jerarquía, con lo cual una transición hacia el pseudoestado H provoca una transición al estado pasado del mismo nivel.

Por ejemplo, la transición disparada por el evento β desde P hacia H provoca inmediatamente una hacia A o B, de acuerdo al estado pasado.Tengamos en mente, que H recuerda el estado pasado en el mismo nivel en el cual se encuentra, en nuestro ejemplo los estados A y B.

El pseudoestado H es otro ejemplo de incorporar memoria adicional a la máquina de estados, en este caso la información no depende de la definición del sistema sino que es simplemente el estado pasado sobre el mismo nivel de jerarquico.

Continuará....