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

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

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.

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.

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.

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).

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.