Programación automática

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 24 de febrero de 2016; las comprobaciones requieren 27 ediciones .

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:

  1. el período de tiempo de ejecución del programa se divide en pasos de autómatas , cada uno de los cuales representa la ejecución de una sección de código específica (la misma para cada paso) con un solo punto de entrada; dicha sección se puede diseñar, por ejemplo, como una función separada y se puede dividir en subsecciones correspondientes a estados individuales o categorías de estados
  2. la transferencia de información entre los pasos del autómata se lleva a cabo únicamente a través de un conjunto de variables explícitamente designado llamado estado del autómata ; entre los pasos del autómata, el programa (o su parte, diseñada al estilo del autómata) no puede contener elementos de estado implícitos, como los valores de las variables locales en la pila, las direcciones de retorno de las funciones, el valor del programa actual contador, etc.; en otras palabras, el estado del programa en dos momentos cualquiera de ingresar al paso del autómata puede diferir entre sí solo por los valores de las variables que componen el estado del autómata (y tales variables deben designarse explícitamente como tal).

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

Un ejemplo usando una máquina de estado

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.

Programa imperativo

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 ; }

Programa de estilo automático

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 ; }

Separación del paso del autómata en una función separada

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:

  1. los pasos individuales del autómata se ejecutan en períodos de tiempo que no se superponen
  2. el único medio de pasar información entre pasos es un estado explícitamente definido (en este caso, una variable state)

Un programa con una tabla de saltos explícita

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 ; }

Uso de características orientadas a objetos

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.

Alcance

La programación automatizada es ampliamente utilizada en la construcción de (autómatas finitos clásicos) y ( ) .

analizadores léxicosanalizadores sintácticosautó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 . En este caso, la programación de estilo FSM es la única alternativa para generar múltiples o subprocesos .

controladas por eventosprocesos

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 , 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 (ver, por ejemplo, ).

UMLde los protocolos de redRFC 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 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).

Refal

El mecanismo de 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.

continuación de Scheme

Alexander Ollongren en su libro describe el llamado método de Viena para describir la semántica de los lenguajes de programación, basado completamente en autómatas formales.

[3]

Un ejemplo de la aplicación del paradigma del autómata es el sistema STAT ; este sistema, en particular, incluye el lenguaje STATL incorporado, que tiene una semántica puramente automática.

[1]

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 argumentan que la programación automática puede desempeñar el papel de la legendaria .

[4]bala de plata

Historia

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 y, sobre todo, con el análisis de textos en lenguajes formales. Uno de los primeros trabajos sobre este tema es el artículo.

la teoría de autómatas[1][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 . 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 en el artículo; el enfoque dado en el artículo satisface la definición anterior de programación automática .

de Peter Naur[6]máquina de Turing

Comparación con programación imperativa y procedimental

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 tradicional consiste en

estilo imperativo
  • conjunto de valores de todas las variables globales y contenidos de memoria dinámica
  • contenido de los registros de propósito general
  • contenido de la pila (incluidas las direcciones de retorno y los valores de las variables locales)
  • el valor actual del contador del programa (es decir, la posición actual en el código del programa)

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

    Relación con la programación orientada a objetos

    En la teoría de , 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 .

    la programación orientada a objetos

    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.

    Lenguajes de programación especializados
    • El lenguaje (Sequential Function Chart) es un industriales .
      • SFClenguaje de programación gráfica ampliamente utilizado para programar controladores lógicos PLC

      En SFC, un programa se describe como una secuencia esquemática de pasos conectados por transiciones.

    •  es un lenguaje de programación gráfico utilizado para la programación en tecnología espacial y de cohetes (" ", " ", " Topol "). Hay un Dragon Editor gratuito.
      • Dragon-schemesBuranSea Launch
    •  es un lenguaje de programación tipo C centrado en describir algoritmos de control complejos en problemas de automatización industrial.
      • El lenguaje Reflex

      Véase también
      • Programación impulsada por eventos

        Notas
        • ↑ 1 2 A. Aho, J. Ullman. La teoría del análisis, la traducción y la compilación = La teoría del análisis, la traducción y la compilación. - M. : MIR, 1978. - T. 1. - 612 p.
        • ↑ Postel, J., ed., Protocolo de control de transmisión, RFC 793
        • ↑ A. Ollongren. Definición de lenguajes de programación mediante la interpretación de autómatas. - M. : MIR, 1977. - 288 p.
        • ↑ Tukkel NI, Shalyto A.A. Programación con Selección Explícita de Estado  // PC World. - 2001. - Nº 9 . - S. 132-138 .
        • ↑ Johnson, WL; Porter, JH; Ackley, SI; Ross, DT Generación automática de procesadores léxicos eficientes utilizando técnicas de estado finito   // Comm . ACM . - 1968. - T. 11 , N º 12 . - S. 805-813 .
        • ↑ Naur, Peter. El diseño del compilador GIER ALGOL Parte II  //  BIT Numerical Mathematics . - 1963. - Septiembre ( ). - . — 0006-3835 . : BF01939983 .vol. 3S. 145-166ISSN -doi10.1007/

        Literatura
      • Polikarpova N.I., Shalyto A.A. . - San Petersburgo. : Pedro, 2009. - 176 p. — ISBN 978-5-388-00692-9 .Programación automática [2]
      • Shalyto A.A. . - San Petersburgo. : Nauka, 1998. - 628 p.Cambiar la tecnología. Algoritmización y programación de tareas de control lógico.
      • Un libro sobre la implementación de la máquina de estado UML2 en C/C++. Dirigido principalmente a la programación de sistemas embebidos en tiempo real.
        • Gráficos de estado UML prácticos en C/C++
      • Boletín científico y técnico de la Universidad Estatal de San Petersburgo ITMO. Número 53. Programación automática. 2008.
        • http://ntv.ifmo.ru/file/journal/61.pdf
      • Zyubin V. E. . - Novosibirsk: Editorial: Novosib. estado un-t, 2006. - 96 p. — ISBN 5-94356-425-X .Programación de sistemas de información y control basados ​​en autómatas finitos: un tutorial.
      • Nepeyvoda N.N. Estilos y métodos de programación. curso de conferencias. guia de estudio - M. : Universidad de Internet de las Tecnologías de la Información, 2005. - S. 145-212. — 316 pág. — ISBN 5-9556-0023-X .
      • Harel, David.    // Sci . computar Programación: diario. - 1987. - _ - .Gráficos de estado: un formalismo visual para sistemas complejosNo. 8pág. 231-274
      • Harel, David; Drusinsky, D. Uso de diagramas de estado para descripción y síntesis de hardware  //  IEEE Trans. Diseño asistido por computadora de circuitos y sistemas integrados: revista. - 1989. - _ - Pág. .No. 8798-807

        Enlaces
      • “Programación automática. Proyectos" (archivo de proyectos con documentación abierta)
      • B. P. Kuznetsov. "Psicología de la programación automática"
      • B. P. Kuznetsov. "Programas automáticos personalizables"