La programación automática es un paradigma de programación , al utilizar un programa o su fragmento como modelo de algún autómata formal . También se conoce otro "paradigma de la programación automática, que consiste en representar entidades de comportamiento complejo en forma de objetos de control automatizados, cada uno de los cuales es un objeto de control y un autómata". Al mismo tiempo, se propone pensar en un programa, como en el control automático, como un sistema de objetos de control automatizado.
Dependiendo de la tarea específica en la programación automática, se pueden usar tanto autómatas finitos como autómatas con una estructura más compleja.
Las siguientes características son decisivas para la programación automática:
La ejecución completa del código de estilo autómata es un bucle (posiblemente implícito) de pasos de autómatas.
El nombre de programación automática también se justifica por el hecho de que el estilo de pensamiento (percepción del proceso de ejecución) cuando se programa en esta técnica reproduce casi exactamente el estilo de pensamiento cuando se compilan autómatas formales (como una máquina de Turing , una máquina de Markov , etc. )
Suponga, por ejemplo, que desea escribir un programa en C que lea texto del flujo de entrada estándar, que consiste en líneas, y para cada línea imprima la primera palabra de esta línea y el salto de línea. Es claro que para esto, mientras lee cada línea, primero debe omitir los espacios, si los hubiere, al principio de la línea; luego lea las letras que componen la palabra e imprímalas hasta que la palabra termine (es decir, la línea termina o se encuentra un espacio en blanco); finalmente, cuando la primera palabra ha sido leída e impresa con éxito, es necesario leer la línea hasta el final sin imprimir nada. Habiendo encontrado (en cualquier fase) un carácter de nueva línea, debe imprimir una nueva línea y continuar desde el principio. Si (nuevamente, en cualquier fase) ocurre la situación de "fin de archivo", se debe detener el trabajo.
Un programa que resuelve este problema en el estilo imperativo tradicional podría verse así ( lenguaje C ):
#incluir <stdio.h> int principal () { intc ; _ hacer { hacer c = obtener char (); mientras ( c == ' ' ); while ( c != ' ' && c != '\n' && c != EOF ) { poner ( c ); c = obtener char (); } poner ( '\n' ); mientras que ( c != '\n' && c != EOF ) c = obtener char (); } mientras ( c != EOF ); devolver 0 ; }El mismo problema se puede resolver pensando en términos de autómatas finitos. Tenga en cuenta que el análisis de una cadena se divide en tres fases: omitir los espacios iniciales, imprimir una palabra y omitir el resto de la cadena. Llamemos a estas tres fases estados before , insidey after. El programa ahora podría verse así:
#incluir <stdio.h> int principal () { enum declara { antes , dentro , después } estado ; intc ; _ estado = antes ; while (( c = getchar ()) != EOF ) { cambiar ( estado ) { caso antes : si ( c == '\n' ) { poner ( '\n' ); } más si ( c != ' ' ) { poner ( c ); estado = dentro ; } romper ; caso interior : cambiar ( c ) { caso ' ' : estado = después ; romper ; caso '\n' : poner ( '\n' ); estado = antes ; romper ; predeterminado : poner ( c ); } romper ; caso después de : si ( c == '\n' ) { poner ( '\n' ); estado = antes ; } } } devolver 0 ; }o así:
#incluir <stdio.h> vacío estático ( * estado ) ( int ); vacío estático antes ( int c ); vacío estático dentro ( int c ); vacío estático después ( int c ); anular antes ( int c ) { si ( c == '\n' ) { poner ( '\n' ); } más si ( c != ' ' ) { poner ( c ); estado = & dentro ; } } vacío dentro ( int c ) { cambiar ( c ) { caso ' ' : estado = & después ; romper ; caso '\n' : poner ( '\n' ); estado = & antes ; romper ; predeterminado : poner ( c ); } } vacío después de ( int c ) { si ( c == '\n' ) { poner ( '\n' ); estado = & antes ; } } int principal () { intc ; _ estado = & antes ; while (( c = getchar ()) != EOF ) { ( * estado )( c ); } devolver 0 ; }A pesar de que el código obviamente se ha vuelto más largo, tiene una ventaja indudable: la lectura (es decir, llamar a una función getchar()) ahora se realiza exactamente en un lugar . Además, cabe señalar que en lugar de los cuatro bucles utilizados en la versión anterior, ahora solo se utiliza un bucle. El cuerpo del ciclo (a excepción de las acciones realizadas en la cabecera) es un paso del autómata , mientras que el propio ciclo marca el ciclo del autómata .
El programa implementa (simula) el funcionamiento de la máquina de estados finitos que se muestra en la figura. La letra N en el diagrama indica el carácter de fin de línea, la letra S indica el carácter de espacio y la letra A indica todos los demás caracteres. En un paso, el autómata hace exactamente una transición, según el estado actual y el carácter leído. Algunas transiciones van seguidas de una impresión del carácter leído; dichas transiciones están marcadas con asteriscos en el diagrama.
En términos generales, no es necesario observar estrictamente la división del código en controladores de estados separados. Además, en algunos casos, el propio concepto de estado puede estar formado por los valores de varias variables, por lo que será casi imposible tener en cuenta todas las combinaciones posibles de ellas. En este ejemplo, puede ahorrar una gran cantidad de código si observa que las acciones realizadas en el carácter de "fin de línea" son independientes del estado. Un programa equivalente al anterior, pero escrito con este comentario en mente, se verá así:
#incluir <stdio.h> int principal () { enum declara { antes , dentro , después } estado ; intc ; _ estado = antes ; while (( c = getchar ()) != EOF ) { si ( c == '\n' ) { poner ( '\n' ); estado = antes ; continuar ; } cambiar ( estado ) { caso antes : si ( c != ' ' ) { poner ( c ); estado = dentro ; } romper ; caso interior : si ( c == ' ' ) estado = después ; más poner ( c ); romper ; caso después de : romper ; } } devolver 0 ; }Fundamental en el programa anterior sigue siendo una selección clara del código responsable del paso del autómata. Esta circunstancia se puede enfatizar aún más fuertemente si el paso del autómata se separa en una función separada.
#incluir <stdio.h> enum state_t { antes , dentro , después }; paso de vacío estático ( enum state_t * state , int * c ) { si ( * estado == antes ) { si ( * c == '\n' ) poner ( '\n' ); si no ( * c != ' ' ) * estado = dentro ; } if ( * estado == dentro ) { si ( * c == ' ' ) { * estado = después de ; } más si ( * c == '\n' ) { poner ( '\n' ); * estado = antes ; } más { poner ( * c ); } } si ( * estado == después ) { si ( * c == '\n' ) { poner ( '\n' ); * estado = antes ; } } } int principal () { intc ; _ enum state_t estado = antes ; while (( c = getchar ()) != EOF ) paso ( & estado , & c ); devolver 0 ; }Este ejemplo demuestra claramente la propiedad principal por la cual se puede considerar que el código está diseñado al estilo de la programación automática:
Un autómata finito, como es sabido, también puede especificarse mediante una tabla de saltos. En términos generales, el código de un programa que simula un autómata finito bien puede reflejar esta propiedad del autómata. En el siguiente programa, una matriz the_tabledefine una tabla de salto. Las filas de la tabla corresponden a los tres estados del autómata, las columnas corresponden a caracteres legibles (la primera columna es un espacio, la segunda columna es un avance de línea, la tercera columna es todos los demás caracteres). Cada celda de la tabla contiene el número del nuevo estado y un signo de la necesidad de imprimir un carácter (en el código anterior, los campos de bits se usan para ahorrar memoria). Por supuesto, en una tarea real, se podría requerir una estructura de tabla mucho más compleja, que contenga, por ejemplo, punteros a funciones para realizar cualquier acción relacionada con las transiciones, pero esto no es necesario en este ejemplo:
#incluir <stdio.h> estados de enumeración { antes = 0 , dentro = 1 _ después = 2 }; rama de estructura typedef { enumeración estados nuevo_estado ; int debería_putchar ; } rama ; static const branch the_table [ 3 ][ 3 ] = { /* ' ' '\n' otros */ /* antes */ { { antes , 0 }, { antes , 1 }, { dentro , 1 } }, /* dentro */ { { después , 0 }, { antes , 1 }, { dentro , 1 } }, /* después */ { { después , 0 }, { antes , 1 }, { después , 0 } } }; paso de vacío estático ( estados de enumeración * estado , int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; rama * b = & la_tabla [ * estado ][ idx2 ]; * estado = b -> nuevo_estado ; si ( b -> debería_putchar ) poner ( c ); } int principal () { intc ; _ enumeración estados estado = antes ; while (( c = getchar ()) != EOF ) paso ( & estado , c ); devolver 0 ; }Si el lenguaje de programación que se utiliza admite funciones orientadas a objetos , tiene sentido encapsular la máquina de estado en un objeto, ocultando los detalles de implementación. Por ejemplo, un programa C++ similar podría verse así:
#incluir <stdio.h> clase StateMachine { estados de enumeración { antes = 0 , dentro = 1 _ después = 2 } estado ; estructura typedef { enumeración estados nuevo_estado ; debería_putchar sin firmar ; } rama ; static const branch the_table [ 3 ][ 3 ]; público : StateMachine () : estado ( antes ) {} void FeedChar ( int c ) { int idx2 = ( c == ' ' ) ? 0 : ( c == '\n' ) ? 1 : 2 ; branch * b = & the_table [ estado ][ idx2 ]; estado = b -> nuevo_estado ; si ( b -> debería_putchar ) poner ( c ); } }; const StateMachine :: rama StateMachine :: la_tabla [ 3 ][ 3 ] = { /* ' ' '\n' otros */ /* antes */ { { antes , 0 }, { antes , 1 }, { dentro , 1 } }, /* dentro */ { { después , 0 }, { antes , 1 }, { dentro , 1 } }, /* después */ { { después , 0 }, { antes , 1 }, { después , 0 } } }; int principal () { intc ; _ Máquina de estados ; _ while (( c = getchar ()) != EOF ) máquina _ FeedChar ( c ); devolver 0 ; }Además, cada estado de la máquina de estado se puede describir como una clase.
#incluir <stdio.h> estado de clase { público : estado ~ virtual () {} Acción de vacío virtual ( int ch , const State *& next_state ) const = 0 ; }; plantilla < claseT > _ clase TState : estado protegido { Estado estático * p ; público : Estado estático * Obtener () { si ( ! pag ) p = nueva T ; devuelve p ; } protegido : Estado () {} }; clase Antes : TState público < Antes > { Acción de vacío virtual ( int ch , const State *& next_state ) const ; }; clase Interior : TState público < Interior > { Acción de vacío virtual ( int ch , const State *& next_state ) const ; }; clase Después : TState público < Después > { Acción de vacío virtual ( int ch , const State *& next_state ) const ; }; plantilla <> Estado * TState < Antes de >:: p = 0 ; plantilla <> Estado * TState < Dentro >:: p = 0 ; plantilla <> Estado * TState < Después >:: p = 0 ; void Before::Action ( int ch , const State *& next_state ) const { if ( ch != ' ' && ch != '\n' ) { putchar ( ch ); siguiente_estado = dentro :: obtener (); } } void Inside::Action ( int ch , const State *& next_state ) const { if ( ch != ' ' && ch != '\n' ) { putchar ( ch ); } más { poner ( '\n' ); siguiente_estado = ( ch == '\n' ? Antes :: Obtener () : Después :: Obtener ()); } } void Después::Acción ( int ch , const Estado *& siguiente_estado ) const { si ( ch == '\n' ) siguiente_estado = antes :: obtener (); } clase FiniteStateMachine { const Estado * estado ; público : FiniteStateMashine () : estado ( Antes :: Obtener ()) {} Paso vacío ( int ch ) { estado -> Acción ( ch , estado ); } }; int principal () { FiniteStateMachine fsm ; int ch ; while (( ch = getchar ()) != EOF ) fsm _ paso ( ch ); devolver 0 ; }Tenga en cuenta que en este ejemplo, usamos la biblioteca C para E/S para evitar la aparición de cambios "innecesarios" (que distraigan) en comparación con el ejemplo anterior.
La programación automatizada es ampliamente utilizada en la construcción de analizadores léxicos (autómatas finitos clásicos) y analizadores sintácticos ( autómatas con memoria push-down ) [1] .
Además, pensar en términos de máquinas de estado (es decir, desglosar la ejecución de un programa en pasos de máquina y pasar información de un paso a otro a través del estado) es esencial al crear aplicaciones controladas por eventos . En este caso, la programación de estilo FSM es la única alternativa para generar múltiples procesos o subprocesos .
A menudo, la noción de estados y máquinas de estados se utiliza para la especificación de programas . Entonces, cuando se diseña software usando UML , los diagramas de máquinas de estado se usan para describir el comportamiento de los objetos. Además, la asignación de estado explícita se utiliza en la descripción de los protocolos de red (ver, por ejemplo, RFC 793 [2] ).
Pensar en términos de autómatas (pasos y estados) también encuentra aplicación para describir la semántica de algunos lenguajes de programación. Así, la ejecución de un programa en lenguaje Refal es una secuencia de cambios en el campo de visión de la máquina Refal o, en otras palabras, una secuencia de pasos de la máquina Refal, cuyo estado es el contenido del campo . de vista (una expresión Refal arbitraria que no contiene variables).
El mecanismo de continuación de Scheme también requiere pensar en términos de estados y pasos para implementarlo, aunque Scheme en sí mismo no es de ninguna manera un autómata. Sin embargo, para poder "congelar" la continuación , es necesario, al implementar el modelo computacional del lenguaje Scheme, combinar todos los componentes del tiempo de ejecución, incluida la lista de acciones que quedan por realizar para completar la cálculo , en una sola unidad, que también se denomina comúnmente continuación . Tal continuación resulta ser un estado del autómata, y el proceso de ejecución del programa consta de pasos, cada uno de los cuales deriva el siguiente valor de continuación del anterior.
Alexander Ollongren en su libro [3] describe el llamado método de Viena para describir la semántica de los lenguajes de programación, basado completamente en autómatas formales.
Un ejemplo de la aplicación del paradigma del autómata es el sistema STAT [1] ; este sistema, en particular, incluye el lenguaje STATL incorporado, que tiene una semántica puramente automática.
También hay propuestas para usar la programación automática como un enfoque universal para crear programas de computadora, independientemente del área temática. Así, los autores del artículo [4] argumentan que la programación automática puede desempeñar el papel de la legendaria bala de plata .
Los primeros casos de aplicación del paradigma de programación de autómatas parecen relacionarse con áreas temáticas en las que se ha desarrollado una teoría algorítmica basada en la teoría de autómatas y, sobre todo, con el análisis de textos en lenguajes formales. [1] Uno de los primeros trabajos sobre este tema es el artículo. [5]
Una de las primeras referencias al uso de técnicas de programación de autómatas, al margen de los desarrollos teóricos basados en máquinas de estados finitos, es un artículo de Peter Naur . [6] En este artículo, el autor llama al enfoque aplicado "enfoque de máquina de Turing" ( Turing machine approach ), pero en realidad no se construye ninguna máquina de Turing en el artículo; el enfoque dado en el artículo satisface la definición anterior de programación automática .
El concepto de estado del programa no es una característica exclusiva de la programación automática. En términos generales, un estado ocurre durante la ejecución de cualquier programa de computadora y es una colección de toda la información que puede cambiar durante la ejecución. Así, el estado de un programa ejecutado en el estilo imperativo tradicional consiste en
Los componentes del estado se pueden dividir en explícitos (como valores de variables) e implícitos (direcciones de retorno y valor de contador de programa).
En el contexto de las definiciones presentadas, un programa diseñado como un modelo de autómata finito puede considerarse un caso especial de un programa imperativo, en el que se minimiza el papel del componente de estado implícito. Si consideramos el programa del autómata en los momentos del comienzo del siguiente paso del autómata, entonces los estados del programa en estos momentos diferirán solo en el componente explícito. Esta circunstancia simplifica enormemente el análisis de las propiedades del programa.
En la teoría de la programación orientada a objetos , se cree que un objeto tiene un estado interno y puede recibir mensajes , responder a ellos, enviar mensajes a otros objetos y cambiar su estado interno en el proceso de procesamiento de mensajes. Más práctico, la noción de llamar al método de un objeto se considera sinónimo de la noción de enviar un mensaje a un objeto .
Así, por un lado, los objetos en la programación orientada a objetos pueden considerarse como autómatas finitos (o, si se prefiere, modelos de autómatas finitos), cuyo estado es una colección de campos internos, mientras que uno o más métodos del El objeto puede ser considerado como un paso del autómata siempre que estos métodos no se llamen a sí mismos ni entre sí directa o indirectamente.
Por otro lado, es obvio que el concepto de objeto es una buena herramienta para implementar el modelo de autómatas finitos. Al aplicar el paradigma de programación de autómatas en lenguajes orientados a objetos, los modelos de autómatas generalmente se representan como clases, el estado del autómata se describe mediante campos internos (privados) de la clase y el código de paso del autómata se formatea como un método de clase, y este método es probablemente el único método público (sin contar los constructores y destructores) que cambia el estado del autómata. Otros métodos públicos pueden servir para obtener información sobre el estado del autómata, pero no cambiarlo. Todos los métodos auxiliares (por ejemplo, controladores de estados individuales o sus categorías) en tales casos, generalmente se eliminan a la parte privada de la clase.
En SFC, un programa se describe como una secuencia esquemática de pasos conectados por transiciones.