Statecharts implementados mediante tablas de estados

El presente artículo tiene por objetivo mostrar las bases de una implementación de máquina de estados Statechart [2,3,5,6] en lenguaje C (compatible con C++), cuyo objetivo fundamental es lograr una representación en código fuente simple, directa, transparente, legible, flexible y compacta, que permita determinar de un sólo vistazo la topología del diagrama que representa, y así lograr una implementación sencilla de modificar, mantener e interpretar. Incluso que facilite la generalización, la reutilización, la transportabilidad, como así también la generación de código automático. Si bien dicha implementación busca maximizar la legibilidad, no descuida ni la eficiencia en el uso de recursos ni la velocidad de ejecución.

Fundamentos de la solución propuesta

El principio de la presente implementación se basa en la representación de máquinas de estados mediante tablas de transición, con lo cual la máquina se construye simplemente inicializando tablas de datos, que luego serán alojadas en ROM. Esto es posible ya que las máquinas NO cambian durante su ejecución, por tal motivo, la implementación en cuestión, trata sus estados, transiciones y reacciones como datos de programa y no como código de programa. Así, crear una nueva máquina implica crear objetos de memoria inicializados en ROM. No obstante, la ejecución de las acciones deben codificarse, es decir, pertenecen a código de programa.
Esta estrategía tiene por ventaja, evitar codificar nuevas máquinas una y otra vez, disminuyendo así, la complejidad de la creación y la generación de posibles errores durante este proceso. Como consecuencia inmediata, una modificación posterior sobre la topología de la misma, implica manipular una simple tabla de datos, sin modificar código fuente. Por el contrario, si la modificación implica un cambio dentro de alguna acción, la misma se resolverá por medio de código de programa.

A su vez, la implementación favorece extraordinariamente la estandarización de la codificación de software basado en máquinas de estados (software reactivo), estableciendo un lenguaje común entre las personas que intervienenen durante el desarrollo, aumentando así la productividad, la calidad y la robustez de las aplicaciones.

Obviamente, esta solución exige que un proceso interprete, en tiempo de ejecución, las tablas de datos, para poner en ejecución las acciones apropiadas. Este último entra en ejecución únicamente ante la ocurrencia de eventos, en cuyo caso, determina la transición de estados, y ejecuta en consecuencia las acciones correspondientes. El interprete se invoca pasándole dos argumentos, el primero es el evento y el otro es la máquina que recibe el evento como entrada.

Independientemente de los Statecharts, la implementación utiliza varios conceptos poderosos de la programación en lenguaje C, como son las tablas de datos para representar parte de programas que no cambian durante su ejecución y la definición de estructuras que surgen de otras ya existentes, utilizando el mecanismo de herencia simple de la programación orientada a objetos, esto favorece la reutilización y la organización del código fuente.

Tablas de transición estados

La siguiente figura muestra la máquina de estados que se utilizará como ejemplo de aplicación, denominada "abstract". Esta se representa mediante el formalismo visual Statechart [2,3,5,6]. Este último consiste principalmente en tres elementos: estados, transiciones y acciones. Los estados son condiciones distinguibles de existencia que persisten por un significativo período de tiempo. Las transiciones son el medio por el cual se produce un cambio de estados en reacción a un evento particular. A su vez, las máquinas de estados ejecutan acciones, comportamientos atómicos, durante una transición, al ingresar a un estado o al abandonarlo.

donde:

• ALPHA, BETA, GAMMA, DELTA, EPSILON: constituyen el alfabeto de entrada (eventos)
• A, B, C, D, E y F: forman el conjunto finito de estados estables (compuestos y básicos).
• act1, act2, act3, act4, act5, act6, act7, act8: definen las acciones de transición.
• entry1, entry2, exit1, exit2 y act4: definen las acciones de entrada.
• exit1, exit2: definen las acciones de salida.
• B: es el estado inicial.
• CH, CL, SH y DH: son pseudoestados choice, conditional,  shallow history y deep history respectivamente.
• cond1, cond2, C1 y C2: son guardas de transición.

A continuación, "abstract" se representa mediante su correspondiente tabla de transiciones de estados, la cual representa la topología de la máquina. A esta tabla se le agrega una tabla adicional, que representa las transiciones emergentes de los pseudoestados conditional (CL) y choice (CH).

De la representación se destacan ciertos aspectos, que requieren especial atención:

• La máquina "abstract" posee una profundidad de tres niveles de anidamiento jerárquico.
• Se incorpora el concepto de transiciones condicionadas, por medio de guardas, las cuales son una condición que debe ser cierta para continuar con la transición en cuestión. 
• Se incorporan acciones al entrar y salir de un estado, generalmente estas acciones se las denomina acciones del tipo Moore, ya que dependen del estado.
• Los pseudoestados choice (CH) y conditional (CL) son puntos transitorios o simplemente estados transitorios, que afectan el camino o destino de una transición, en función de condiciones o expresiones lógicas (guardas).
• El pseudoestado history (SH/DH) significa que el estado compuesto "recuerda" su último estado básico activo. El pseudoestado shallow history significa que la historia se aplica al contexto de anidamiento actual, los estados anidados más profundamente no son afectados por la presencia de este pseudoestado en contexto de mayor nivel de anidamiento. Mientras que el pseudoestado deep history se aplica hacia abajo para todos los niveles de anidamiento.

El siguiente fragmento de código representa la topología de la máquina "abstract" utilizando la implementación propuesta. Permitiendo construir la máquina de estados en tiempo de compilación, simplemente inicializando las tablas de datos (tablas de transición). Para simplificar aún más el proceso de creación de la máquina, la inicialización de las tablas se encapsula por medio de macros, siendo estas resueltas "silenciosamente" por el preprocesador durante la compilación.

/* Transition table of stable states */
RKH_CREATE_TRANSITION_TABLE( A )
 RKH_TR( GAMMA,   NULL,  act3, &CL ),
RKH_END_TRANSITION_TABLE

RKH_CREATE_TRANSITION_TABLE( B )
 RKH_TR( ALPHA,   NULL,  act4, &D ),
 RKH_TR( DELTA,   NULL,  NULL, &DH ),
RKH_END_TRANSITION_TABLE

RKH_CREATE_TRANSITION_TABLE( C )
 RKH_TR( EPSILON,  NULL,  act4, &C ),
 RKH_TR( DELTA,   NULL,  NULL, &SH ),
RKH_END_TRANSITION_TABLE

RKH_CREATE_TRANSITION_TABLE( D )
 RKH_TR( ALPHA,   NULL,  act1, &D ),
 RKH_TR( BETA,   cond1,  act2, &B ),
RKH_END_TRANSITION_TABLE

RKH_CREATE_TRANSITION_TABLE( E )
 RKH_TR( ALPHA,   NULL,  act5, &F ),
RKH_END_TRANSITION_TABLE

RKH_CREATE_TRANSITION_TABLE( F )
 RKH_TR( ALPHA,   NULL,  act5, &E ),
 RKH_TR( DELTA,   cond2, act2, &B ),
 RKH_TR( EPSILON, NULL,  act2, &CH ),
RKH_END_TRANSITION_TABLE

/* Branch table of conditional pseudostate */
RKH_CREATE_BRANCH_TABLE( CL )
 RKH_BRANCH( C2,  act6,  &C ),
 RKH_BRANCH( ELSE,  act7,  &D ),
RKH_END_BRANCH_TABLE

/* Branch table of choice pseudostate */
RKH_CREATE_BRANCH_TABLE( CH )
 RKH_BRANCH( C1,  act3,  &B ),
 RKH_BRANCH( ELSE,  act8,  &E ),
RKH_END_BRANCH_TABLE

Nota: para mayor detalle ver RKH [1].


Definiendo atributos de estados y pseudoestados

Para representar completamente un Statechart, a diferencia de una máquina plana tradicional (Mealy/Moore), se requieren definir atributos a los estados y pseudoestados, los cuales no están explicitos en las tablas de transición, por ejemplo, las acciones de entrada y salida de estado, el estado por defecto de un estado compuesto, entre otros. La siguiente figura muestra los atributos del estado básico (o subestado) F, del estado compuesto (o superestado) D, y de los pseudoestados CH, CL, SH y DH.

Siguiendo la idea de la implementación, los atributos también se definen en tiempo de compilación, como así también se alojan en ROM, como lo indica el siguiente fragmento de código.
Para simplificar aún más el proceso de definición e inicialización de estados y pseudoestados, se recurre nuevamente al uso de macros.

/* Basic states (substates)*/
RKH_CREATE_BASIC_STATE( B, 2, entry1, NULL,  RKH_ROOT,  NULL );
RKH_CREATE_BASIC_STATE( C, 3, NULL,   exit2, &D,  NULL );
RKH_CREATE_BASIC_STATE( E, 4, NULL,   NULL,  &A,  NULL );
RKH_CREATE_BASIC_STATE( F, 5, entry2, exit2, &A,  NULL );

/* Composite states (superstates)*/
RKH_CREATE_COMP_STATE(  A, 1, entry1, exit1, &D,  &A, &SH );
RKH_CREATE_COMP_STATE(  D, 3, NULL,   NULL,  RKH_ROOT,  &E, &DH );

/* Choice pseudostate */
RKH_CREATE_CHOICE_STATE( CH, 6 );

/* Conditional (junction) pseudostate */
RKH_CREATE_COND_STATE( CL, 7 );

/* Shallow history pseudostate */

RKH_CREATE_SHALLOW_HISTORY_STATE( SH, 8, &A );

/* Deep history pseudostate */
RKH_CREATE_DEEP_HISTORY_STATE( DH, 9, &D );

Tanto las acciones de entrada y salida de estados, las guardas y acciones de transición se referencian en las tablas por medio de punteros a función. Adicionalmente, las macros referencian internamente las correspondientes tablas de transición.


Nota: para mayor detalle ver RKH [1].

La siguiente figura muestra los atributos que definen los estados estables y los pseudoestados. La tabla ha sido coloreada especialmente para indicar los atributos comunes.

La manera de representar y definir los estados y pseudoestados (atributos), utilizando el lenguaje C, es mediante estructuras. Estas se definen agrupando los atributos comunes.

/**
 * \brief 
 * Maintains the basic information of a state.
 */

typedef struct rkhbase_t
{
    /** 
     *  \brief
     *  State type.
     *
     * Contains the type of a particular state and can have 
     * the following values:
     *
     * - \b RKH_COMPOSITE:   composite state.
     * - \b RKH_BASIC:       basic state.
     * - \b RKH_CHOICE:      choice pseudostate.
     * - \b RKH_CONDITIONAL: conditional pseudostate.
     * - \b RKH_SHISTORY:    shadow history pseudostate.
     * - \b RKH_DHISTORY:    deep history pseudostate.
     */

    HUInt type;     

    /** 
     *  \brief
     * State ID. 
     * This number isn't internally used by RKH framework.
     */

    #if RKH_SMA_EN_STATE_ID == 1
    HUInt id;
    #endif
} RKHBASE_T;


/**
 * \brief
 * Describes the common properties of regular states (basic, 
 * composite, and submachine).
 */

typedef struct rkhst_t
{
    /** 
     *  \brief
     * Maintains the basic information of state.
     */

    struct rkhbase_t base;

    #if RKH_SMA_EN_HCAL == 1
    /** 
     *  \brief
     * Points to entry action.
     */

    RKHENT_T enter;

    /** 
     *  \brief
     * Points to exit action.
     */

    RKHEXT_T exit;

    /** 
     *  \brief
     * Points to state's parent.
     */

    RKHROM struct rkhst_t *parent;
    #endif
} RKHST_T;


/**
 * \brief
 * Describes a basic state.
 */

typedef struct rkhsbsc_t
{
    RKHST_T st;

    /** 
     *  \brief
     * Points to state transition table.
     */

    RKHROM struct rkhtr_t *trtbl;

    /** 
     *  \brief
     * Points to event preprocessor.
     *
     * Aditionally, by means of single inheritance in C it could be 
     * used as state's abstract data.
     * Aditionally, implementing the single inheritance in C is very 
     * simply by literally embedding the base type, RKHPPRO_T in 
     * this case, as the first member of the derived structure.
     * 
     * This argument is optional, thus it could be declared as NULL.
     *
     * Example:
     *  
     *  \code
     * static
     * RKHE_T
     * preprocessor( RKHEVT_T *pe )
     * {
     *  ...
     * }
     *  
     * typedef struct
     * {
     *  RKHPPRO_T prepro;  // extend the RKHPPRO_T class
     *  unsigned min:4;
     *  unsigned max:4;
     *  char *buff;
     * } SDATA_T;
     *
     * static const SDATA_T option = { preprocessor, 4, 8, token1 };
     *
     * RKH_CREATE_BASIC_STATE( S111, 0, set_x_1, 
     *     NULL, &S11, preprocessor ); 
     * RKH_CREATE_BASIC_STATE( S22, 0, set_x_4, 
     *     NULL, &S2, (RKHPPRO_T*)&option ); 
     * \endcode
     */

    #if RKH_SMA_EN_PPRO == 1
    RKHPPRO_T prepro;
    #endif
} RKHSBSC_T;


/**
 * \brief
 * Describes a composite state.
 */

typedef struct rkhscmp_t
{
    RKHST_T st;

    /** 
     *  \brief
     * Points to state transition table.
     */

    RKHROM struct rkhtr_t *trtbl;

    /** 
     *  \brief
     * Points to event preprocessor.
     *
     * Aditionally, by means of single inheritance in C it could be 
     * used as state's abstract data.
     * Aditionally, implementing the single inheritance in C is very 
     * simply by literally embedding the base type, RKHPPRO_T in 
     * this case, as the first member of the derived structure.
     * 
     * This argument is optional, thus it could be declared as NULL.
     *
     * Example:
     *  
     *  \code
     * static
     * RKHE_T
     * preprocessor( RKHEVT_T *pe )
     * {
     *  ...
     * }
     *  
     * typedef struct
     * {
     *  RKHPPRO_T prepro;  // extend the RKHPPRO_T class
     *  unsigned min:4;
     *  unsigned max:4;
     *  char *buff;
     * } SDATA_T;
     *
     * static const SDATA_T option = { preprocessor, 4, 8, token1 };
     *
     * RKH_CREATE_BASIC_STATE( S111, 0, set_x_1, 
     *     NULL, &S11, preprocessor ); 
     * RKH_CREATE_BASIC_STATE( S22, 0, set_x_4, 
     *     NULL, &S2, (RKHPPRO_T*)&option ); 
     * \endcode
     */

    #if RKH_SMA_EN_PPRO == 1
    RKHPPRO_T prepro;
    #endif

    #if RKH_SMA_EN_HCAL == 1
    /** 
     *  \brief
     * Points to state's default child.
     */

    RKHROM void *defchild;

    /** 
     *  \brief
     * Points to state's history. 
     */

    RKHROM struct rkhshist_t *history;
    #endif
} RKHSCMP_T;


/**
 * \brief 
 * Describes the conditional pseudostate.
 */

typedef struct rkhscond_t
{
    /**
     *  \brief
     * Maintains the basic information of state.
     */

    struct rkhbase_t base;

    /** 
     *  \brief
     * Points to branch table.
     */

    RKHROM struct rkhtr_t *trtbl;
} RKHSCOND_T;


/**
 * \brief 
 * Describes the choice pseudostate.
 */

typedef struct rkhschoice_t
{
    /**
     *  \brief
     * Maintains the basic information of state.
     */

    struct rkhbase_t base;

    /** 
     *  \brief
     * Points to branch table.
     */

    RKHROM struct rkhtr_t *trtbl;
} RKHSCHOICE_T;


/**
 * \brief 
 * Describes the history pseudostate
 * It can be either be shallow or deep.
 */

typedef struct rkhshist_t
{
    /** 
     *  \brief
     * Maintains the basic information of state.
     */

    struct rkhbase_t base;

    /** 
     *  \brief
     * Points to state's parent.
     */

    RKHROM RKHST_T *parent;

    /** 
     *  \brief
     * Points to RAM memory location which stores
     * the state's history.
     */
    RKHROM RKHST_T **target;
} RKHSHIST_T;

Nota: para mayor detalle ver RKH [1].

Definición de una transición de estados

De acuerdo a la tabla anterior, a continuación se muestra la estructura que representa y define una transición. De esta forma, la tabla de transición de un estado, es simplemente un arreglo de estructuras RKHTR_T.

/**
 *  \brief
 *  Describes the state transition. 
 *
 *  Transitions represent the response of a state machine to events. 
 *  Any event that is not explicitly listed as causing an event to 
 *  occur in a given state is quietly discarded should it occur.
 */

typedef struct rkhtr_t
{
    /**  
     *  \brief
     *  Triggering event.
     */

    RKHE_T event;
 
    /** 
     *  \brief
     * Points to guard function.
     */

    RKHGUARD_T guard;
 
    /**  
     *  \brief
     *  Points to transition action.
     */

    RKHACT_T action;

    /**  
     *  \brief
     *  Points to target state.
     */

    RKHROM void *target;
} RKHTR_T;

Nota: para mayor detalle ver RKH [1].

Definición de una máquina de estados

De igual manera que los estados y pseudoestados, la máquina también requiere sus propios atributos, los cuales establecen su estado inicial, su acción de inicialización, entre otros. La especificación UML 2.0 [4], define a la máquina de estados como un estado adicional, de nombre top-state, también denominado root por ser el primer estado en el anidamiento jerárquico.

/* State machine (top-state) */
RKH_SMA_CREATE( ABSTRACT_T,
                0, 
                abstract,         /* state machine */ 
                0, 
                HCAL, 
                &B, 
                abstract_init,    /* initialization */
                NULL );

Nota: para mayor detalle ver RKH [1].

Próximo estado, estructuras derivadas y herencia simple

Dado que la columna "Next State" o estado destino de las tablas de transición, referencia a cualquier tipo de estado o pseudoestado, como lo indica la figura, el tipo de datos utilizado en la estructura RKHTR_T para tal fin es void*, tal como lo indica la definición del miembro target. De esta manera en tiempo de compilación la tabla puede inicializarse sin problema alguno.

Por otro lado, en tiempo de ejecución el interprete de las tablas debe determinar a partir del miembro target cuál es el siguiente estado/pseudoestado de la transición en progreso y fundamentalmente cuál es su tipo. Ahora, ¿cómo puede determinarse qué tipo de estado/pseudoestado referencia target, siendo este del tipo abstracto void*?. Para ello se utiliza el operador cast [8], aún así, ¿a qué tipo de datos debe convertirse target para determinar el tipo?. Bien, sabiendo que el tipo de estado/pseudoestado (miembro type) es un atributo común entre todos los objetos y este pertenece a la estructura RKHBASE_T, la conversión de tipo se realiza a esta última, como ejemplifica el siguiente fragmento de código. Resumiendo, este es el mecanismo utilizado para determinar, en tiempo de ejecución, el tipo de estructura (estado/pseudoestado) a partir de una puntero a void, que referencia una estructura desconocida.

#define CAST( _type, _obj )   ((_type*)(_obj))

next_type = ((RKHBASE_T*)(tr->target))->type;
switch( next_type )
{
    case RKH_COMPOSITE:
        default = ((RKHCMP_T*)(tr->target))->defchild;
        break; 
    case RKH_BASIC:
        parent = CAST(RKHHIST_T, tr->target)->parent;
        break; 
    ...
}

(3-4) Conociendo el tipo, se realiza la conversión adecuada.
(6-7) Si el siguiente estado es uno compuesto, y se requiere su estado por defecto, se convierte target al tipo RKHSCMP_T para acceder finalmente al miembro defchild.
(10) En este caso es del tipo básico, del cual se requiere su ancestro inmediato o padre.
(1) La conversión de tipo (type casting) es algo engorrosa y generalmente ofusca el código, con lo cual es preferible encapsularla en una macro, y aplicarla como en (10).


El mecanismo descripto se aplica como consecuencia de la detallada definición de estructuras intervinientes. Específicamente, la técnica empleada para crear las estructuras se basa en definir una estructura base y agregarla como primer miembro de la estructura que se requiere obtener (o derivar). Por ejemplo, la estructura RKHSCMP_T se obtiene (o deriva) de la estructura base RKHST_T, la cual, a su vez, se obtiene (o deriva) de la estructura RKHBASE_T, así, RKHSCMP_T es una estructura derivada de RKHST_T y esta última derivada de RKHBASE_T, la siguiente figura clarifica el ejemplo. La capacidad de obtener nuevas estructuras derivadas de otras ya existentes, es similar al mecanismo de herecencia simple [X] de la programación orientada a objetos.

Conclusiones

El artículo resume los principios utilizados para implementar Statecharts mediante tablas de datos en lenguaje C (compatible con C++). La misma es una alternativa a las bien conocidas maneras de implementar diagramas de estados, cuyo objetivo fundamental es lograr una representación en código fuente simple, directa, transparente, legible, flexible y compacta, de formal tal que la misma permita determinar de un sólo vistazo la topología del diagrama que representa, y así lograr una implementación sencilla de modificar, mantener e interpretar. Si bien la implementación en cuestión  busca maximizar la legibilidad, no descuida ni la eficiencia en el uso de recursos ni la velocidad de ejecución.

El principio de la presente implementación se basa en la representación de máquinas de estados mediante tablas de transición alojadas en ROM. Esto es posible ya que las máquinas NO cambian durante su ejecución, por tal motivo, la implementación en cuestión, trata sus estados, transiciones y reacciones como datos de programa y no como código de programa. Así, crear una nueva máquina implica crear objetos de memoria inicializados en ROM. No obstante, la ejecución de las acciones deben codificarse, es decir, pertenecen a código de programa.

Esta estrategía tiene por ventaja, evitar codificar nuevas máquinas una y otra vez, disminuyendo así, la complejidad de la creación y la generación de posibles errores durante este proceso. Como consecuencia inmediata, una modificación posterior sobre la topología de la misma, implica manipular una simple tabla de datos, sin modificar código fuente. Por el contrario, si la modificación implica un cambio dentro de alguna acción, la misma se resolverá por medio de código de programa.

A su vez, la implementación favorece extraordinariamente la estandarización de la codificación de software basado en máquinas de estados (software reactivo), estableciendo un lenguaje común entre las personas que intervienenen durante el desarrollo, aumentando así la productividad, la calidad y la robustez de las aplicaciones.

Por otro lado, independientemente de los Statecharts, la implementación utiliza varios conceptos poderosos de la programación en lenguaje C, como son las tablas de datos para representar parte de programas que no cambian durante su ejecución y la definición de estructuras que surgen de otras ya existentes, utilizando el mecanismo de herencia simple de la programación orientada a objetos, esto favorece la reutilización y la organización del código fuente.

Referencias

[1] RKH, “RKH Sourceforge download site,”, http://sourceforge.net/projects/rkh-reactivesys/

[2] D. Harel, "Statecharts: A Visual Formalism for Complex Systems", Sci. Comput. Programming 8 (1987), pp. 231–274.
[3] D. Harel and H. Kugler - "The Rhapsody Semantics of Statecharts", Lecture Notes in Computer Science, Vol. 3147, Springer-Verlag, 2004, pp. 325-354.
[4] Object Management Group, “Unified Modeling Language: Superstructure version 2.1.1,” formal/2007-02-05, Febrary 2007.
[5] B. P. Douglass, “State machines and Statecharts,”
[6] B. P. Douglass, “UML and Statecharts,”, Embedded.com, June 17, 2003
[7] RKH, “Reference Manual,”, http://rkh-reactivesys.sourceforge.net/

[8] Dennis M. Ritchie, Brian Kernighan, "C Programming Language", (2nd Edition), April 1, 1988, pp. 41-44.