www.osgg.net

.....

Representación de maquinas de estados finitos en componentes y en el lenguaje de programación Java (20.ABR.05) Omar Salvador gómez gómez

Introducción
El objetivo de este trabajo es realizar una exploración para determinar las ventajas e implicaciones de agregar la noción de estado tanto a un componente como a un lenguaje de programación orientado a objetos. En este reporte de investigación el lenguaje de programación que se usará para explicar la propuesta de solución será Java.

 

Declaración del problema
Existen varias maneras de representar maquinas de estados en lenguajes de programación orientados a objetos, ya sea utilizando tablas indexadas [7], usando el operador switch [3] el cual es anidado junto con sentencias if, usando redes de Petri [5], construyendo un mecanismo el cual utiliza métodos virtuales [1]. Gracias a estas técnicas los objetos pueden comportarse como
maquinas de estados finitos.

¿Qué pasaría si se conociera el estado de un componente u objeto de manera externa?, ¿Qué ventajas e implicaciones tendrían el usar este enfoque?, Este trabajo se centrará en resolver estas preguntas desde dos perspectivas: implementando maquinas de estados finitos en un lenguaje de programación actual, en este caso Java y proponer un mecanismo a un leguaje de programación para que sea posible implementar maquinas de estados finitos de manera mas transparente.

De acuerdo a la primera perspectiva un caso en particular sería el poder preguntar sobre el estado en el que se encuentre algún componente el cual esté representado como una maquina de estados finitos. De acuerdo al estado en el que se encuentre el componente, el usuario puede realizar alguna acción. De esta manera en cualquier momento el componente por medio de sus operaciones puede proporcionar el estado en el que se encuentra.

 

Trabajo previo
De acuerdo a Shalyto [3] el principal uso de las maquinas de estados ha sido en el hardware, un ejemplo de esto son los controladores lógicos programables conocidos como PLC los cuales tienen una cantidad pequeña de memoria y son programados de acuerdo a maquinas de estados.

Otro uso que han tenido las maquinas de estado es en ayudar a modelar problemas teóricos de programación como es el caso de los compiladores. Una de las tendencias actuales es el poder representar estados en lenguajes de programación orientados a objetos. Los inicios de esta técnica surgen de los sistemas basados en eventos. Un sistema basado en eventos [4] es una interconexión de componentes en la cual los componentes se comunican unos a otros por medio de eventos. Por ejemplo el sistema envía un evento en particular el cual es atendido por un componente interesado en ese evento. Este tipo de sistemas es también conocido como sistemas reactivos [3]. El programar este tipo de sistemas bajo un enfoque orientado a objetos además del uso de eventos y con ayuda de un enfoque de maquina de estado se le conoce como programación orientada a objetos basada en estados [2].

 

Usando programación orientada a objetos basada en estados las acciones son asignadas a arcos (grafos de transición), de esta manera es posible representar secuencias de acciones, las cuales son reacciones a las acciones de entrada correspondientes, por lo que este enfoque esta basado sobre los paradigmas orientado a objetos y basado en autómatas de estados finitos. Un autómata de estados finitos M es una quíntupla M = (S, I, d, S0, F) donde:

· S es el conjunto finito de estados.

· I es un alfabeto finito de símbolos de entrada.

· d es la transición de un estado a otro S ´ I ® S.

· S0 es el estado inicial.

· F son los estados de aceptación.

Un autómata de estados finitos puede representarse de manera grafica utilizando statecharts [6]. Existe una relación entre statecharts y los lenguajes de programación orientados a objetos, en ambos es posible representar el mecanismo de herencia [1,6]. Usando statecharts un estado puede contener subestados así como en un lenguaje de programación orientado a objetos un conjunto de objetos puede extender propiedades de otro objeto. Gracias a esta relación es posible representar el mecanismo de herencia de los statecharts en lenguajes de programación orientados a objetos.

 

Solución propuesta
En este trabajo de investigación se presentan dos propuestas de solución: la primera se centra en poder representar maquinas de estados finitos en el actual lenguaje de programación Java, la segunda propuesta es proponer un mecanismo al lenguaje Java el cuál permita de manera transparente representar maquinas de estados finitos. Las dos propuestas serán descritas a través de un ejemplo.

La primera propuesta de solución consiste en utilizar el enfoque de programación orientada a objetos basada en estados en el actual lenguaje de programación Java, este enfoque se describirá con un sencillo ejemplo. El ejemplo consiste en implementar un componente que representa una lista, el cual realiza una serie de acciones que son: inicializar la lista, insertar un elemento en la lista, borrar un elemento de la lista y ordenar los elementos que se encuentren en la lista.

La primera actividad a realizar es representar el componente como una maquina de estados
finitos, dicha representación se muestra en la Figura 1.

 

 

Figura 1. Representación del componente Lista en una maquina de estados finitos.

Una vez representado el componente Lista como una maquina de estados finitos se identifican los posibles estados en los que se puede encontrar el componente en un tiempo determinado, estos estados son: inicializar, en espera, obteniendo lista, ordenando lista, borrando elemento o agregando elemento.

Una vez identificados los estados el siguiente paso es representar el componente con un diagrama de clases, el diagrama de clases que se propone y que se muestra en la Figura 2 es un poco diferente al diagrama de clases tradicional el cual incluye nombre de la clase, atributos y operaciones. Sin embargo a este diagrama se le agregaron cuatro secciones más que son: States, Actions, Events, Control Transitions.

· States. En esta sección se especifican los nombres de los estados que contiene la maquina de estados finitos.

· Actions. En esta sección se especifican las acciones que se deben de realizar cuando se realiza una transición entre dos estados.

· Events. En este apartado se especifica el nombre de cada uno de los eventos que tiene la maquina de estados finitos.

· Control Transitions. En esta sección se especifican las transiciones de la maquina de estados finitos.

De esta manera el implementador del componente puede conocer más información sobre como esta modelada la maquina de estados finitos que contiene el componente.

Figura 2. Diagrama de clases propuesto para representar maquinas de estados finitos.

El componente debe de implementar la interfaz Runnable, ya que continuamente esta escuchando y atendiendo a los diferentes eventos de la maquina de estados. De acuerdo a un evento en particular que el usuario del componente genere, el componente realizará una acción por ejemplo si el usuario del componente genera un evento del tipo init, el componente Lista recibe el evento y realiza la acción de inicializarLista(), dentro de cada uno de los métodos se cambia el estado para que en cualquier momento el usuario del componente pueda conocer el estado del componente Lista.

A continuación en la Figura 3 aparece un pequeño pseudocódigo que muestra la manera en como el componente Lista recibe algún evento y lo atiende.

1 public class Lista implements Runnable{

2 Lista listaOrdenada;

3 public void run(){

4 while( true ){

5 switch( eventType ){

6 case eventInit: inicializarLista();

7 break;

8 case eventSort: listaOrdenada = ordenar();

9 break;

. …

. }

. }

. }

. }

Figura 3. Fragmento de código en lenguaje Java del componente Lista.

En la linea 1 la clase Lista implementa la interfaz Runnable con la finalidad de que una instancia de esta clase se encuentre continuamente recibiendo y atendiendo los eventos previamente definidos en el diagrama de clase de la Figura 2. En la linea 5 se utilizá una estructura de selección la cual de acuerdo a un evento dado se ejecuta una operación, por ejemplo en caso de que se reciba el evento sort que es representado por el identificador eventSort en la linea 8, se realizá la acción ordenar.

Un vez descrito un pequeño fragmento de codigo del componente Lista, a continuacion se muestra en la Figura 4 cómo un cliente usa el componente Lista.

1 public class Cliente{

2 Lista componenteLista = new Lista();

3 if ( componenteLista.getActualState().equals( ”inicializar” ) )

4 System.out.println( ”Espere un momento la lista se esta inicializando” );

5 if ( componenteLista.getActualState().equals( ”En espera” ) ){

6 EventType eventSort = new EventSort(”sort”);

7 componenteLista.sendEvent( eventSort );

8 }

9 }

Figura 4. Fragmento de código de un cliente que esta usando el componente Lista.

En la linea 2 se declara un identificador llamado componenteLista del tipo Lista el cual contiene la especificación de la maquina de estados finitos que aparece en la Figura 1. En la linea 3 se le pregunta en que estado se encuentra el componente si el componente esta en el estado de inicializar el cliente manda un mensaje al usuario. En la línea 5 si el componente Lista se encuentra en el estado En espera se declara un identificador del tipo EventType y se crea un objeto del tipo EventSort con el nombre del evento sort, una vez creado el evento EventSort se le envía al componente a través del método sendEvent, de esta manera en la Figura 3 el componente Lista realiza la acción ordenar de la línea 8.

 

Una vez presentada la primer propuesta de solución que consiste en utilizar el enfoque de programación orientada a objetos basada en estados en el actual lenguaje de programación Java se concluye lo siguiente:

 

Las ventajas de conocer en cualquier momento los estados del componente es que se tiene mas control sobre las acciones que se quieran realizar, por ejemplo no realizar alguna acción hasta que el componente se encuentre en cierto estado lo cual se demuestra en la Figura 4 líneas 3 y 5. Otra ventaja es que en caso de que el componente genere un error se puede saber el estado en el que se encontraba el componente, de esta manera el usuario del componente tiene más información por lo que puede determinar alguna acción a realizar.

 

Una de las implicaciones que se encontró al usar este enfoque es que el componente debe de ejecutarse como un subproceso del sistema en este caso de la Java Virtual Machine[8] para que continuamente este recibiendo y atendiendo los eventos definidos en la maquina de estados finitos, Por lo que es la única manera de informarle al implementador del componente sobre los estados en que se encuentra el componente.

 

La segunda propuesta de solución consiste en proponer un mecanismo a un leguaje de programación para que sea posible implementar maquinas de estados finitos de manera mas transparente, el lenguaje al que se propone este mecanismo es Java. Primeramente se propone agregar una clase a la librería base de Java como se muestra en la Figura 5. La clase FSM contiene los métodos para conocer en que estado se encuentra el componente que implementa esta clase, además de los eventos que contiene es posible conocer las acciones y transiciones de dicho componente. La clase FSM debe implementar la interfaz Runnable para que cuando un componente sea implementado como un FSM la Java Virtual Machine[8] lo interprete por lo que esta creará un subproceso o hilo para que el componente reciba y atienda los eventos previamente especificados por la maquina de estados finitos.

 

Figura 5. Diagrama de clase propuesto a incluirse en la librería base de Java.

Partiendo del supuesto de que la clase FSM este incluida en la librería base de Java, a continuación se muestra un ejemplo para implementar la maquina de estados finitos de la Figura 1. En la Figura 6 se proponen algunas palabras reservadas para que de manera mas transparente el lenguaje Java pueda implementar maquinas de estados finitos.

En las líneas de código 01-22 se especifica el comportamiento de una maquina de estados finitos, se deben de declarar las cuatro secciones que son: states, actions, events y transitions. En cada una de las secciones se especifica las partes de la FSM, en la sección de actions se declaran las acciones como si fueran métodos para que posteriormente dentro de la sección class se sobrescriban estos métodos con la funcionalidad deseada, esto se muestra en las líneas 24-28.

Una vez implementado la definición de la maquina de estados finitos se implementa la clase que para este ejemplo es Lista, a esta clase se debe de especificar que es una maquina de estados finitos por medio de la palabra reservada is seguida de la clase FSM previamente descrita. En las líneas 29-35 se muestra una estructura de selección la cual dado un cierto evento ejecuta una operación.

01 definitionFSM {

02 states = { Inicializar, En espera, Obteniendo lista, Ordenando lista,

Borrando elemento, Agregando elemento }

04 actions {

05 private List obtenerLista();

06 private List ordenar();

07 private void borrar( Object elemto );

08 private void agregar( Object elemento );

09 private void inicializar();

10 }

11 events = { wait, get, sort, delete, insert, init }

12 transitions = { Inicializar>>wait>>En espera,

En espera>>get>>Obteniendo lista,

En espera>>sort>>Ordenando lista,

En espera>>delete>>Borrando elemento,

En espera>>insert>>Agregando elemento,

En espera>>init>>inicializar,

Obteniendo lista>>wait>>En espera,

Ordenando lista>>wait>>En espera,

Borrando elemento>>wait>>En espera,

Agregando elemento>>wait>>En espera }

22 }

23 public class Lista is FSM{

24 private List ordenar(){

…

26 return listaOrdenada;

…

28 }

29 switch( eventType ){

30 case eventInit: inicializarLista();

31 break;

32 case eventSort: listaOrdenada = ordenar();

33 break;

…

35 }

36 }

Figura 6. Fragmento de código del componente Lista.

Una vez descrito el componente Lista en la Figura 7 se muestra parte del código de un cliente que usa el componente Lista. En la línea 2 se declara un identificador llamado componenteLista del tipo Lista el cual contiene la especificación de la maquina de estados finitos que aparece en la Figura 1.

En la línea 3 se le pregunta en que estado se encuentra el componente, si el componente esta en el estado de inicializar el cliente manda un mensaje al usuario. En la línea 5 si el componente Lista se encuentra en el estado En espera se declara un identificador del tipo EventType y se crea un objeto del tipo EventSort con el nombre del evento sort, una vez creado el evento EventSort se le envía al componente a través del método sendEvent, de esta manera en la Figura 6 el componente Lista realiza la acción ordenar de la línea 32.

1 public class Cliente{

2 Lista componenteLista = new Lista();

3 if ( componenteLista.getActualState().equals( ”inicializar” ) )

4 System.out.println( ”Espere un momento la lista se esta inicializando” );

5 if ( componenteLista.getActualState().equals( ”En espera” ) ){

6 EventType eventSort = new EventSort(”sort”);

7 componenteLista.sendEvent( eventSort );

8 }

9 }

Figura 7. Fragmento de código del un cliente que usa el componente Lista.

Las conclusiones de esta segunda propuesta son las siguientes: ya que el lenguaje de programación permite manejar maquinas de estados finitos es mucho mas fácil para el implementador del componente conocer los estados de este ya que la clase FSM contiene la información de los estados, acciones, eventos y transiciones.

El lenguaje queda abierto para poder implementar o no maquinas de estados por medio de la palabra reservada is. Las implicaciones de usar este enfoque son: es necesario modificar la JVM para que maneje el concepto de estados, y de igual manera que en la primer propuesta, en este enfoque el componente también se ejecuta continuamente como un subproceso de la JVM, por lo que es la única manera de que el componente pueda recibir y atender a los eventos.

 

Referencias

1. D. Shopyrin, “Object oriented implementation of state based logic”,

http://www.codeproject.com/cpp/statebased.asp

2. A.A. Shalyto, “Technology of automata based programming”, 2003

http://www.codeproject.com/gen/design/abp.asp

3. A.A. Shalyto, “Logic Control and Reactive Systems: Algorithmization and Programming”, Automation and Remote Control, Vol. 62, No. 1, 2001, pp. 1-29
4. I. Sommerville, “Software Engineering”, Addison Wesley, 2001, pp. 227-229
5. A. Newman, S. M. Shatz, X. Xie, “An aproach to object system modeling by state-based object Petri nets”
6. D. Harel, “StateCharts: a visual formalism for complex systems”, science of computer programming, 1987, #8
7. O. Lehrmann Madsen, “Towards integration of state machines and object-oriented languages”, 1999,

http://www.cit.dk/COT/reports/reports/Case2/26/cot-2-26.pdf

8. T. Lindholm, Y. Frank, “The Java Virtual Machine Specification”, Addison-Wesley, 1999