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

Cualquier programa de un solo hilo que se ejecute en una máquina con una cantidad limitada 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 de pila, datos actualmente intercambiados en la memoria virtual, incluso el contenido de los archivos relevantes. En otras palabras, habrá un lote de estados en ese modelo de estado finito, incluso para programas bastante triviales.

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

Un modelo de autómata de empuje hacia abajo 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 quedes atascado en la sección de definición formal.

Los autómatas de empuje hacia abajo se utilizan para modelar cálculos generales. Las máquinas de Turing son similares , pero IIRC no son idénticas, aunque sus capacidades de cálculo son equivalentes .

  

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

     

Honestamente, no sé de dónde provino este genio cerebral. sí sé que las gramáticas sensibles al contexto son más poderosas que las libres, y que las gramáticas sensibles al contexto no pueden analizarse usando un simple autómata de empuje hacia abajo. Incluso sé que, si bien es posible analizar cualquier gramática libre de contexto sin ambigüedades en un tiempo lineal, generalmente se necesita más que un autómata de empuje (determinista) para hacer eso. Entonces, ¿cómo podría terminar creyendo que un autómata de empuje hacia abajo es equivalente a una máquina de Turing? Es extraño.

     

Tal vez estaba pensando en un autómata push-down con alguna maquinaria adicional agregada, pero eso sería como contar con un autómata finito como equivalente a un autómata push-down (solo agregar y explotar una pila).

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

Es posible modelar un solo 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ías los estados válidos entre (no durante) las llamadas de método. De nuevo, generalmente tendrá muchos estados de los que preocuparse: es algo que podría usar como modelo teórico, pero no querría enumerar todos esos estados, excepto tal vez 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 es también lo que normalmente se hace al definir un analizador usando un modelo de autómata de empuje hacia abajo. 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 p. El problema de los 4 mil millones de estados para un entero: no enumere todos esos estados, solo incluya la variable entera. En cierto sentido, sigue siendo parte del estado del autómata de empuje hacia abajo, 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 entender algo, si se puede pensar que esa cosa es 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: es casi seguro que no. No parece haber una teoría matemática formal para la POO de la misma manera que el cálculo lambda y / o la lógica combinatoria subestiman la programación funcional, o las máquinas de Turing subyacen a la programación imperativa antigua ordinaria.

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

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

No, no prácticamente de todos modos. Una máquina de estado finito normalmente solo recuerda un dato: su estado actual.

Una aplicación típica de un FSM es el lexing o el análisis. Por ejemplo, cuando estamos haciendo lexing, es (normalmente) 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 NÚMERO en el que estemos leyendo los dígitos de un número. Si el siguiente carácter que leemos es un dígito, nos quedamos en el estado NÚMERO. Si se trata de un espacio o una pestaña, devolveríamos los dígitos y luego avanzamos a algún estado de 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 y piezas que técnicamente no encajan bien con un FSM combinado con el FSM en sí. Por ejemplo, cuando estamos leyendo los 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 podrá calcular fácilmente el valor del número.

El FSM en sí mismo tiene algunas limitaciones, no tiene ningún mecanismo de conteo. Considere, por ejemplo, un lenguaje que usó "/ " para iniciar un comentario y " /" para finalizar un comentario. Su lexer probablemente tendría un estado COMENTARIO que ingresó cuando vio un token '/ '. En este momento no tiene forma (a menos que se agregue otro estado como COMMENT2) 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 ese caso, un estado COMMENT3, y así sucesivamente. En algún momento, sin embargo, se va a cansar de agregar más estados, y eso determinará la profundidad máxima de anidamiento que permite comentarios. Con alguna otra forma de analizador (es decir, no es una máquina de estado pura, sino algo que tiene algo de memoria que le permita contar), puede rastrear su profundidad de anidamiento directamente, de modo que permanezca en el estado COMENTARIO hasta que alcance un token de comentario cercano que equilibra el primero, por lo que su contador vuelve a 0 y deja el estado COMENTARIO.

Sin embargo, como dije, cuando agregas un contador como ese, lo que tienes ya no es realmente un FSM. Al mismo tiempo, está en realidad 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 el software, lo mantendrá razonablemente "puro". En particular, el software reaccionará a la entrada actual basándose solo en el estado actual y el valor de la entrada en sí. Si la reacción depende de mucho de cualquier otra cosa, generalmente no lo llamarán una máquina de estado (al menos si saben de lo que 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 informáticos 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 en los que tiene n instancias de un objeto seguidas de n instancias de otro objeto porque las máquinas de estados finitos no pueden escribir n en una variable. Solo pueden leer la entrada y cambiar a un estado.