Máquina de estados finitos: ¿mal diseño?

Question

¿Las máquinas de estado finito generalmente se consideran como mal diseño en OOP?

He oído eso mucho. Y, después de tener que trabajar en una pieza de C++ realmente antigua e indocumentada que hace uso de ella, tiendo a estar de acuerdo. Fue un dolor de depurar.

¿qué ocurre con la legibilidad/mantenibilidad?

Answer 1

Las FSM nunca deben considerarse malas. Son demasiado útiles, pero las personas que no están acostumbradas a ellos a menudo los considerarán pesados.

Existen numerosas formas de implementar una con OOP. Algunos son más feos que otros. Tus chicos de bajo nivel usarán declaraciones de interruptor, tablas de salto o incluso "goto".

Si está buscando una forma más limpia de hacerlo, recomendaría Boost's State Chart library, que está diseñado solo para implementar diagramas de estados UML en C++. Hace uso de técnicas de plantilla modernas, para hacer las cosas más legibles. También funciona muy bien.

Answer 2

Creo que si el código está bien documentado, no hay ningún problema para implementarlo utilizando un enfoque OOP. La mayoría de los C/C++ utilizan para implementar FSM utilizando declaraciones de interruptor que a veces pueden comprometer la legibilidad si la máquina es grande.

Recientemente me necesita para analizar un lenguaje regular, e implementado un FSM usando el enfoque de programación orientada a objetos, la legibilidad del código y la capacidad de mantenimiento eran buenas. Quiero decir, mucho mejor que usar grandes declaraciones de cambio.

Un consejo, en un primer momento, he implementado el FSM containg estados y los estados que contienen las transiciones. Sin embargo, en mi caso resultó ser un mejor enfoque para tener una clase para representar el FSM que contiene una colección de estados y otra de transiciones. Me resultó más fácil clonar las máquinas (era un requisito para mí) y tener una función de transición más pequeña.

espero que ayude, Carlos.

Answer 3

diría que las máquinas de estados finitos son mucho más fáciles de depurar que otras maneras de resolver los mismos problemas (problemas como la equiparación de los lenguajes regulares). Lo bueno de los FSM es todo en el nombre ... es posible que tenga una máquina de estado con 15 estados, por lo que puede dibujar un diagrama en un pedazo de papel que muestre todas las transiciones. Puede usar el diagrama para descubrir las propiedades útiles del sistema, como qué cadenas acepta y cómo entra en los estados de error. Con sistemas más complicados, la diagramación es a menudo difícil o imposible.

Incluso la gente que dice "GOTOS son malos" piensan que son la forma correcta para implementar máquinas de estado. (Por supuesto, algunas personas piensan que los gotos son siempre malvados ... pero no puedes complacer a todos).

Answer 4

No se pudo decir lo que dicen.

Pero OO y FSM sorta atacan diferentes dominios problemáticos. En un dominio donde los objetos interactúan, eso requiere un enfoque orientado a objetos. En un dominio donde el mundo está en un estado u otro, eso requiere un diseño de FSM.

Siendo realistas, usted puede mezclar diseños de/a diferentes niveles de abstracción, que van a salir más limpio que el uso de sólo uno o el otro.

Answer 5

Las máquinas de estado finito son una herramienta para lograr cierto fin. Como cualquier herramienta, pueden ser abusados ​​también.

Ellos no son el más atento de herramientas, pero el trabajo que son buenos es casi imposible de lograr por otros medios (y por lo general cualquier otro enfoque es entonces condenado a ser un desastre horrible, mil veces peor que la máquina).

El trabajo está funcionando en condiciones en las que los estados de espera clásicos están prohibidos.

Tengo que leer la pantalla táctil. Para leer la posición, tengo que intercambiar unos 15 comandos sobre SPI. Necesito buenas 100 lecturas por segundo. Tengo que esperar aproximadamente 1 microsegundo después de cada comando, para que desaparezca la correspondiente bandera ocupada antes de que pueda continuar. También hay varias otras operaciones que deben poder obtenerse a través de la misma interfaz, como establecer el contraste, cambiar modos, encender o apagar la luz de fondo, leer la temperatura. Si realizara while(BUSY_BIT); por cada espera, me comería toda la CPU en cuestión de minutos. Si hiciera sched_yield() o usleep(1), nunca alcanzaría la cantidad de lecturas que quiero. La única forma es una máquina de estados finitos.

Pero también hay formas de hacer que la máquina de estados finitos funcione bien. Oculta la máquina detrás de escena y dales a los desarrolladores funciones para trabajar.

Mi experiencia de trabajo hasta ahora estaba dominada por 2 sistemas basados ​​en 3 máquinas de estados finitos diferentes.

1. un gran portal web, donde en cada paso recupera algunos datos de la base de datos y, basándose en ello, prepara más consultas. En el último paso, usa los datos para generar HTML. Cada tarea, un módulo de página web, se implementó como una clase PHP que hereda del motor. Estado fue preservado en variables de clase. Cada paso era una función separada. Al final de un paso, las consultas almacenadas se optimizaban y enviaban al motor, a través de cachés, y las respuestas se proporcionaban nuevamente al original.
2. un dispositivo integrado con muchos subsistemas. Task Pump se usa. Cada módulo registra un controlador que se llama muchas veces por segundo desde el bucle principal. El controlador puede preservar el estado en variables estáticas o de clase, con estados. Esta multitarea cooperativa permite una memoria mucho más pequeña que ejecutar todo en subprocesos separados, permite la priorización manual de las tareas registrándolas dos veces y hace que el subproceso se ejecute con alta prioridad, eclipsando al resto del sistema.
3. semi-intérprete. Esa pantalla táctil. Las llamadas de función y sus estados de espera están registrados, pero cada uno se llama solo una vez y luego se elimina de la cola de programas. El intérprete se llama como una tarea de taskpump, ejecutando un número limitado de funciones hasta encontrar una función marcada como estado de espera (o exceder la cantidad de funciones a ser llamadas). Luego continúa hasta que el estado de espera desaparece. Otras tareas ponen en cola trabajos como (a veces largas) secuencias de funciones para ser ejecutadas, luego esperan el resultado. De esta forma puedo limitar el número de estados que necesito crear a unos 4 donde necesito resultados. Si el comando es "enviar lejos, nunca verificar resultado" como "establecer contraste", no necesitan estados discretos. Por lo tanto, los estados reales son "esperar el evento y registrar los datos solicitados", "esperar la medición" y "leer los resultados y asignarlos correctamente".

El código sería el doble de simple y tres veces más claro si se escribe de forma estructural o secuencial. Excepto que no funcionaría, o funcionaría con un rendimiento abismal.

Answer 6

State Machine se puede utilizar para representar el comportamiento de cualquier clase. Si el orden de los eventos entrantes no es relevante para un comportamiento de Clase (Clase combinatoria), el uso del Modelo de Estado no ofrece ningún beneficio especial.

Sin embargo, si el comportamiento de una Clase depende del orden de los eventos entrantes (Clase secuencial) State Machine representa la mejor opción para el análisis e implementación del comportamiento.

Si le interesa la legibilidad/mantenibilidad, use representaciones gráficas. Los ejemplos del comportamiento de las clases que pertenecen a diferentes dominios de ingeniería se presentan de forma gráfica y ejecutable en http://www.StateSoft.org -> State Machine Gallery.

-Janusz

Answer 7

FSM puede ser fácil de entender y mantener si el código está estructurado de la manera correcta. He implementado una MEF en trabajos anteriores, aquí hay una plantilla de esqueleto:

FSM