¿Se puede ver un programa orientado a objetos como una máquina de estados finitos?

13

Esta podría ser una pregunta filosófica / fundamental, pero solo quiero aclararla.

Según tengo entendido, una máquina de estados finitos es una forma de modelar un sistema en el que la salida del sistema no solo dependerá de las entradas actuales, sino también del estado actual del sistema. Además, como su nombre lo indica, una máquina de estados finitos puede segmentarse en un número N finito de estados con su estado y comportamiento respectivos.

Si esto es correcto, ¿no deberían todos los objetos con datos y miembros de funciones ser un estado en nuestro modelo orientado a objetos, convirtiendo cualquier diseño orientado a objetos en una máquina de estados finitos?

Si esa no es la interpretación de un FSM en el diseño de objetos, ¿qué quieren decir exactamente las personas cuando implementan un FSM en software? ¿Me estoy perdiendo de algo?

Gracias

Peretz
fuente
66
Computer + software es una máquina de estado siempre que restrinja la memoria, el espacio en disco y otros tipos de almacenamiento (como Internet). Tan pronto como se permite la interfaz con Internet u otro hardware externo (implica almacenamiento ilimitado), esto se parece más a una máquina Turing. ¿Has oído hablar de una frase 'Turing completo'? De todos modos, los programas funcionales y los orientados a obj terminan como código de ensamblaje. No sé Haskel (un lenguaje funcional puro) / mónadas, pero debe haber una relación interesante entre eso y una máquina de Turing.
Trabajo
Además del punto de Jobs, cualquier forma de no determinismo también excede tanto la máquina de estado como los modelos de máquina de Turing. En Internet, tiene varias máquinas no sincronizadas, pérdida de datos a través de conexiones imperfectas, etc. Incluso con una computadora simple de un solo núcleo, tiene una entrada no determinista del usuario, pero normalmente ignora ese problema y finge todos los la entrada fue conocida de antemano.
Steve314
@ Steve314: Formalmente, los autómatas deterministas están en un solo estado. Cada entrada conduce a un nuevo estado. Para autómatas no deterministas, cada entrada puede conducir a múltiples estados. Un autómata determinista con 2 ^ N estados puede emular un autómata no determinista con N estados.
Kevin Cline
@cline: en este caso, tienes toda la razón, pero creo que lo que tenía en mente era el tipo de concurrencia y variación de tiempo que ocurre en una máquina del mundo real, cosas como un núcleo que funciona un poco más lento porque hace demasiado calor , la hora exacta en que los datos están debajo del cabezal de lectura, etc. Todo esto encaja en el modelo de autómatas finitos no deterministas que describe, por supuesto, por lo que tiene toda la razón, pero el número de estados será increíblemente enorme. Supongo que también podría haber tenido medidas continuas, como esas temperaturas, como parte del estado del sistema (no solo las consecuencias).
Steve314

Respuestas:

16

Cualquier programa de subproceso único que se ejecute en una máquina con una cantidad finita de almacenamiento puede modelarse como una máquina de estado finito. Un estado particular en la máquina de estados finitos representará los valores específicos de todo el almacenamiento relevante: variables locales, variables globales, almacenamiento dinámico, datos actualmente intercambiados en la memoria virtual, incluso el contenido de los archivos relevantes. En otras palabras, habrá muchos estados en ese modelo de estado finito, incluso para programas bastante triviales.

Incluso si el único estado que tiene su programa es una sola variable global de un tipo entero de 32 bits, eso implica al menos 2 ^ 32 (más de 4 mil millones) de estados. Y eso ni siquiera tiene en cuenta el contador del programa y la pila de llamadas.

Un modelo de autómata push-down es más realista para este tipo de cosas. Es como un autómata finito, pero tiene un concepto incorporado de pila. Sin embargo, no es realmente una pila de llamadas como en la mayoría de los lenguajes de programación.

Hay una explicación de Wikipedia , pero no te atasques en la sección de definición formal.

Los autómatas pushdown se utilizan para modelar cálculos generales. Las máquinas de Turing son similares , pero el IIRC no es idéntico, aunque sus capacidades de cálculo son equivalentes .

Gracias a Kevin Cline por señalar el error anterior: como también señala Wikipedia , los autómatas de empuje son más potentes que las máquinas de estados finitos, pero menos potentes que las máquinas de Turing.

Sinceramente, no sé de dónde pedo cerebral vino de - Me hago saber que las gramáticas sensibles al contexto son más poderosos que libre de contexto, y que las gramáticas sensibles al contexto no se puede analizar usando un simple autómata de empujar hacia abajo. Incluso sé que si bien es posible analizar cualquier gramática libre de contexto inequívoca en tiempo lineal, generalmente se necesita más que un autómata (determinista) para hacer eso. Entonces, cómo podría terminar creyendo que un autómata de empuje es equivalente a una máquina de Turing es extraño.

Tal vez estaba pensando en un autómata push-down con un poco de maquinaria adicional agregada, pero eso sería como contar un autómata finito como equivalente a un autómata push-down (simplemente agregue y explote una pila).

Los autómatas push-down son importantes en el análisis. Estoy familiarizado con ellos en ese contexto, pero nunca los he estudiado realmente como modelos informáticos de computación, por lo que no puedo dar muchos más detalles de los que ya tengo.

Es posible modelar un único objeto OOP como máquina de estados finitos. El estado de la máquina estará determinado por los estados de todas las variables miembro. Normalmente, solo contaría los estados válidos entre (no durante) las llamadas al método. Una vez más, generalmente tendrá que preocuparse por muchos estados: es algo que podría usar como modelo teórico, pero no querría enumerar todos esos estados, excepto quizás en un caso trivial.

Sin embargo, es bastante común modelar algún aspecto del estado de un objeto utilizando una máquina de estados finitos. Un caso común es la IA para los objetos del juego.

Esto también es lo que normalmente se hace al definir un analizador utilizando un modelo de autómata push-down. Aunque hay un conjunto finito de estados en un modelo de estado, esto solo modela parte del estado del analizador: la información adicional se almacena en variables adicionales junto con ese estado. Esto resuelve, por ejemplo, el problema de 4 mil millones de estados por un número entero: no enumere todos esos estados, solo incluya la variable entera. En cierto sentido, sigue siendo parte del estado del autómata pushdown, pero es un enfoque mucho más manejable que en efecto dibujar 4 mil millones de burbujas de estado en un diagrama.

Steve314
fuente
1
"Es posible modelar un solo objeto OOP como máquina de estados finitos". Cierto, pero débil. No es posible". Es una cuestión de definición. El trabajo de un lenguaje de programación es expresar un FSM en una notación ordenada. OOP es una implementación de un FSM con notación más simple para todos los estados.
S.Lott
1
@ S.Lott: Sí, pero la mayoría de la gente no piensa que un objeto OOP exprese un FSM, al menos no la mayor parte del tiempo. El uso del nombre "máquina de estado" tiende a implicar que está utilizando alguna implementación específica, como el patrón de diseño de estado o una variable miembro de ID de estado. "Modelar como una máquina de estado" a menudo también implica algo sobre la especificación o la documentación de diseño, distinta de la implementación de esa clase. Por lo tanto, modelar una clase como un modelo de estado finito subjetivamente significa algo más que simplemente proporcionar el código fuente de la clase.
Steve314
"La gente no piensa". Cierto. Y un profundo problema. Todos los programas son máquinas de estado. Tienen muchos estados. Eso es lo que requiere la prueba "Turing Complete" para un lenguaje de programación. Es una regla muy, muy fuerte (y absoluta). En lugar de sugerir que es "posible", es más como "necesario" y "suficiente".
S.Lott
1
-1: los autómatas pushdown no son tan potentes como las máquinas de Turing.
Kevin Cline
1
@kevin cline, gracias, ¡y en qué estaba pensando ! Editado para golpear ese bit. A pesar de lo que dije sobre el estudio formal, sé mejor que eso y debería haberlo sabido en aquel entonces.
Steve314
5

El problema no es si algo "es" o "no es" una máquina de estados finitos. Una máquina de estados finitos es un modelo mental que puede ser útil para comprender algo si esa cosa puede considerarse como una.

Normalmente, el modelo de máquina de estados finitos se aplica a cosas con un pequeño número de estados, como una gramática regular o el secuenciador de instrucciones de una computadora.

Mike Dunlavey
fuente
1

Para responder a su pregunta directamente: casi seguro que no. No parece haber una teoría matemática formal para OOP de la forma en que el cálculo lambda y / o la lógica combinatoria subyacen a la programación funcional, o las máquinas de Turing en la programación imperativa antigua y ordinaria.

Vea esta pregunta de stackoverflow para más información.

Supongo que la falta de una teoría matemática subyacente es la razón por la cual todos saben qué es un "objeto" cuando lo ven, pero nadie ve los "objetos" de la misma manera que cualquier otra persona.

Bruce Ediger
fuente
0

No, no prácticamente de todos modos. Una máquina de estados finitos normalmente solo recuerda una pieza de datos: su estado actual.

Una aplicación típica de un FSM es lexing o parsing. Por ejemplo, cuando hacemos lexing, (normalmente) es bastante fácil codificar las acciones para cada entrada posible en términos de un estado actual y el valor de la entrada.

Por ejemplo, podríamos tener un estado NUMBER en el que estamos leyendo los dígitos de un número. Si el siguiente carácter que leemos es un dígito, permanecemos en el estado NUMBER. Si se trata de un espacio o una pestaña, devolveremos los dígitos y luego avanzaremos a un estado WHITE_SPACE, o algo en ese orden.

Ahora, es cierto que en un FSM típico (especialmente uno que está implementado en software) terminamos con partes que técnicamente no se ajustan a un FSM mezclado con el FSM en sí. Por ejemplo, cuando leemos dígitos de un número, con frecuencia va a guardar la posición del primer dígito, de modo que cuando llegue al final pueda calcular fácilmente el valor del número.

El FSM en sí tiene algunas limitaciones: no tiene un mecanismo de conteo. Considere, por ejemplo, un lenguaje que usó "/ " para comenzar un comentario y " /" para finalizar un comentario. Su lexer probablemente tendría un estado COMENTARIO al que ingresó cuando vio un token '/ '. No tiene forma en este punto (salvo agregar otro estado como COMMENT2) para detectar otro "/ " y darse cuenta de que se trata de un comentario anidado. Más bien, en el estado de comentario, reconocerá */que le dice que deje el estado de comentario, y cualquier otra cosa lo deja en el estado de comentario.

Como se mencionó, ciertamente podría incluir un estado COMMENT2 para un comentario anidado, y en eso, un estado COMMENT3, etc. Sin embargo, en algún momento, te cansarás de agregar más estados, y eso determinará la profundidad máxima de anidación que permites para los comentarios. Con alguna otra forma de analizador (es decir, no una máquina de estado puro, sino algo que tenga algo de memoria para que cuente), puede seguir su profundidad de anidamiento directamente, de modo que permanezca en el estado COMENTARIO hasta llegar a un token de comentario cercano que equilibra el primero, por lo que su contador vuelve a 0 y deja el estado COMENTARIO.

Como dije, sin embargo, cuando agrega un contador como ese, lo que tiene ya no es realmente un FSM. Al mismo tiempo, en realidad está bastante cerca, específicamente, lo suficientemente cerca como para que pueda simular el contador simplemente agregando más estados.

Sin embargo, en un caso típico, cuando alguien habla de implementar un FSM en software, lo mantendrá razonablemente "puro". En particular, el software reaccionará a la entrada actual basándose únicamente en el estado actual y el valor de la entrada en sí. Si la reacción depende de algo más, generalmente no lo llamarán una máquina de estados (al menos si saben de qué están hablando).

Jerry Coffin
fuente
"su estado actual" puede incluir una gran cantidad de información. Un FSM puede contar trivialmente al tener estados para cada número que contará. Es finito (a diferencia de una máquina de Turing) pero todavía es perfectamente capaz de contar. Creo que podrías necesitar un mejor ejemplo.
S.Lott
El software de su teléfono celular es una colección de máquinas de estado horriblemente complejas que recuerdan muchos datos y los interpretan de acuerdo con el estado actual.
Mawg dice que reinstalar a Mónica el
-2

No creo que la respuesta aceptada sea completamente correcta.

No puede modelar un programa arbitrario escrito en un lenguaje Turing Complete, ya sea orientado a objetos o no, como una máquina de estados finitos. Casi todos los lenguajes de computadora modernos, como Java, C ++ o Smalltalk, son Turing Complete.

Por ejemplo, no puede crear una máquina de estados finitos para reconocer una secuencia de objetos donde tiene n instancias de un objeto seguidas de n instancias de otro objeto porque las máquinas de estados finitos son incapaces de escribir n en una variable. Solo pueden leer la entrada y cambiar a un estado.

James Fremen
fuente
esto simplemente repite los puntos hechos y explicados en las respuestas publicadas hace 3 años, por ejemplo, en este
mosquito