Programación basada en autómatas

La programación basada en autómatas es un paradigma de programación en el que el programa o parte de él se considera un modelo de una máquina de estados finitos (FSM) o cualquier otro autómata formal (a menudo más complicado) (véase teoría de autómatas ). A veces se introduce un conjunto potencialmente infinito de estados posibles, y dicho conjunto puede tener una estructura complicada, no solo una enumeración.

La programación basada en máquinas de estados finitos es generalmente la misma, pero, formalmente hablando, no cubre todas las variantes posibles, ya que FSM significa máquina de estados finitos, y la programación basada en autómatas no necesariamente emplea FSM en sentido estricto.

Las siguientes propiedades son indicadores clave para la programación basada en autómatas:

• El período de tiempo de ejecución del programa está claramente separado hasta los pasos del autómata . Cada paso es efectivamente una ejecución de una sección de código (la misma para todos los pasos) que tiene un único punto de entrada. Esa sección se puede dividir en subsecciones que se ejecutarán según los diferentes estados, aunque esto no es necesario.
• Cualquier comunicación entre los pasos del autómata sólo es posible a través del conjunto de variables explícitamente anotadas, denominadas estado del autómata . Entre dos pasos cualesquiera, el programa no puede tener componentes implícitos de su estado, como valores de variables locales, direcciones de retorno, el puntero de instrucción actual, etc. Es decir, el estado de todo el programa, tomado en dos momentos cualesquiera de la entrada a un paso del autómata, sólo puede diferir en los valores de las variables que se consideran como el estado del autómata.

Toda la ejecución del código basado en autómatas es un ciclo de los pasos del autómata.

Otra razón para utilizar la noción de programación basada en autómatas es que el estilo de pensar del programador sobre el programa en esta técnica es muy similar al estilo de pensamiento utilizado para resolver tareas matemáticas utilizando máquinas de Turing , algoritmos de Markov , etc.

Considere la tarea de leer un texto de la entrada estándar línea por línea y escribir la primera palabra de cada línea en la salida estándar . Primero omitimos todos los caracteres de espacio en blanco iniciales , si los hay. Luego imprimimos todos los caracteres de la primera palabra. Finalmente omitimos todos los caracteres finales hasta que se encuentra un carácter de nueva línea . Siempre que se encuentra una secuencia de caracteres de nueva línea que no está al principio de la secuencia, imprimimos solo el primero y omitimos los restantes; de lo contrario, omitimos todos. A continuación, reiniciamos el proceso en la siguiente línea. Al encontrar la condición de fin de archivo (independientemente de la etapa), nos detenemos.

Un programa tradicional en C que realiza la tarea anterior podría verse así:

#incluir <ctype.h> #incluir <stdio.h> 
 


int principal ( vacío ) { int c ;  
   

  hacer { hacer { c = getchar (); } mientras ( isspace ( c )); 
     
        
      

    mientras ( ! isspace ( c ) && c != EOF ) { putchar ( c ); c = getchar (); } mientras ( c != '\n' && c != EOF ) { c = getchar (); } si ( c == '\n' ) { putchar ( c ); } } mientras ( c != EOF );      
      
        
    
    
            
        
    
    
        
      
    
      

  devuelve 0 ; } 

Por ejemplo, compilar y ejecutar el programa anterior en esta entrada:

$ clang  programa.c && ( printf "\t\v\f\r \n\n\t\v\f\r foo bar baz\n\n\t\v\f\r qux quux corge" | ./a.out )     

rendimientos:

Foo 
qux

La misma tarea se puede resolver pensando en términos de máquinas de estados finitos . El análisis de una línea tiene tres etapas: omitir los caracteres de espacio en blanco iniciales, imprimir los caracteres de la primera palabra y omitir los caracteres finales. Llamemos a estos estados de autómata BEFOREy . Una versión del programa basada en autómatas podría verse así: INSIDEAFTER

#incluir <ctype.h> #incluir <stdio.h> 
 

enumeración Estado { ANTES , DENTRO , DESPUÉS };    


int main ( void ) { int c ; enumeración Estado s = ANTES ;  
   
      

  mientras (( c = getchar ()) != EOF ) { cambiar ( s ) { caso ANTES : si ( ! isspace ( c )) { putchar ( c ); s = DENTRO ; } romper ; caso DENTRO : si ( c == '\n' ) { putchar ( c ); s = ANTES ; } de lo contrario si ( isspace ( c )) { s = DESPUÉS ; } de lo contrario { putchar ( c ); } romper ; caso DESPUÉS : si ( c == '\n' ) { putchar ( c ); s = ANTES ; } romper ; } }      
      
       
          
          
            
        
        
        
       
            
          
            
            
            
          
          
        
          
        
       
            
          
            
        
        
        
    
  

  devuelve 0 ; } 

Aunque el programa ahora parece más largo, tiene al menos una ventaja significativa: sólo hay una instrucción de lectura (es decir, llamada a la getcharfunción). Además de eso, sólo hay un bucle en lugar de los cuatro que tenía la versión tradicional. El cuerpo del whilebucle es el paso del autómata y el bucle en sí es el ciclo del paso del autómata. El programa implementa el trabajo de una máquina de estados finitos que se muestra en el diagrama de estados.

La propiedad más importante del programa es que la sección del código del paso del autómata está claramente localizada. Con una función explícita steppara el paso de automatización, el programa demuestra mejor esta propiedad:

#incluir <ctype.h> #incluir <stdio.h> 
 

enumeración Estado { ANTES , DENTRO , DESPUÉS };    


void paso ( enumeración Estado * const s , int const c ) { cambiar ( * s ) { caso ANTES : si ( ! isspace ( c )) { putchar ( c ); * s = DENTRO ; } romper ; caso DENTRO : si ( c == '\n' ) { putchar ( c ); * s = ANTES ; } de lo contrario si ( isspace ( c )) { * s = DESPUÉS ; } de lo contrario { putchar ( c ); } romper ; caso DESPUÉS : si ( c == '\n' ) { putchar ( c ); * s = ANTES ; } romper ; } }        
    
     
        
        
          
      
      
      
     
          
        
          
          
          
        
        
      
        
      
     
          
        
          
      
      
      
  



int main ( void ) { int c ; enumeración Estado s = ANTES ;  
   
      

  mientras (( c = getchar ()) != EOF ) { paso ( & s , c ); }      
     
  

  devuelve 0 ; } 

El programa ahora demuestra claramente las propiedades básicas del código basado en autómatas:

• Los períodos de tiempo de ejecución de los pasos del autómata no pueden superponerse;
• La única información que se pasa del paso anterior al siguiente es el estado del autómata especificado explícitamente .

Un autómata finito se puede definir mediante una tabla de transición de estados cuyas filas representan los estados actuales, las columnas representan las entradas y las celdas representan los próximos estados y acciones a realizar.

En términos generales, un programa basado en autómatas puede utilizar este enfoque de forma natural. Con una matriz bidimensional explícita transitionspara la tabla de transición de estados, el programa utiliza este enfoque:

#incluir <ctype.h> #incluir <stdio.h> 
 

enumeración Estado { ANTES , DENTRO , DESPUÉS };    


vacío nop ( int const c ) {}    


void print ( int const c ) { putchar ( c ); }    
  



estructura Rama { enumeración Estado const siguiente_estado ; void ( * acción )( int ); };  
     
   



struct Branch const transitions [ 3 ][ 3 ] = { // nueva línea espacio en blanco otras Entradas/Estados {{ ANTES , & nop }, { ANTES , & nop }, { DENTRO , & print }}, // antes de {{ ANTES , & print }, { DESPUÉS , & nop }, { DENTRO , & print }}, // dentro de {{ ANTES , & print }, { DESPUÉS , & nop }, { DESPUÉS , & nop }} // después };     
  
           
          
              



void paso ( enumeración Estado * const s , int const c ) { int const fila = ( * s == ANTES ) ? 0 : ( * s == DENTRO ) ? 1 : 2 ; int const columna = ( c == '\n' ) ? 0 : isspace ( c ) ? 1 : 2 ; struct Rama const * const b = & transiciones [ fila ][ columna ]; * s = b -> siguiente_estado ; b -> acción ( c ); }        
                  
                
        
    
  



int main ( void ) { int c ; enumeración Estado s = ANTES ;  
   
      

  mientras (( c = getchar ()) != EOF ) { paso ( & s , c ); }      
     
  

  devuelve 0 ; } 

Si el lenguaje de implementación admite programación orientada a objetos , una refactorización sencilla del programa consiste en encapsular el autómata en un objeto, ocultando así sus detalles de implementación. El programa en C++ que utilice el estilo orientado a objetos podría verse así:

#incluir <ctype.h> #incluir <stdio.h> 
 

enumeración Estado { ANTES , DENTRO , DESPUÉS };    


estructura Rama { enumeración Estado const siguiente_estado ; void ( * acción )( int ); };  
     
   



clase StateMachine { público : StateMachine (); void feedChar ( int );  
  
    
     

  protegido : 
void estático nop ( int ); void estático print ( int );      
      

  privado : 
enumeración Estado _state ; estructura estática Rama const _transitions [ 3 ][ 3 ]; };      
        



StateMachine :: StateMachine () : _state ( ANTES ) {}  


void StateMachine :: feedChar ( int const c ) { int const fila = ( _estado == ANTES ) ? 0 : ( _estado == DENTRO ) ? 1 : 2 ; int const columna = ( c == '\n' ) ? 0 : isspace ( c ) ? 1 : 2 ; struct Branch const * const b = & _transitions [ fila ][ columna ]; _estado = b -> siguiente_estado ; b -> acción ( c ); }    
                  
                
        
    
  



Máquina de estado vacía :: nop ( int const c ) {}    


void StateMachine :: print ( int const c ) { putchar ( c ); }    
  



struct Branch const StateMachine :: _transitions [ 3 ][ 3 ] = { // nueva línea espacio en blanco otras Entradas/Estados {{ ANTES , & nop }, { ANTES , & nop }, { DENTRO , & print }}, // antes de {{ ANTES , & print }, { DESPUÉS , & nop }, { DENTRO , & print }}, // dentro de {{ ANTES , & print }, { DESPUÉS , & nop }, { DESPUÉS , & nop }} // después };     
  
           
          
              



int main () { int c ; Máquina de estados m ;  
   
   

  mientras (( c = getchar ()) != EOF ) { m . feedChar ( c ); }      
    
  

  devuelve 0 ; } 

Para minimizar los cambios que no están directamente relacionados con el tema del artículo, se utilizan las entradas/salidas getchar y putcharfunciones de la biblioteca estándar de C.

El patrón de diseño de estados es una forma de que un objeto cambie su comportamiento en tiempo de ejecución de acuerdo con su estado interno sin recurrir a grandes sentencias condicionales o búsquedas en tablas gracias a llamadas de funciones virtuales. Su principal ventaja sobre el código que utiliza grandes sentencias condicionales es que el código específico de estado se distribuye entre diferentes objetos en lugar de localizarse en un bloque monolítico, lo que mejora la capacidad de mantenimiento. Sus principales ventajas sobre el código que utiliza tablas de transición de estado son que las llamadas de funciones virtuales suelen ser más eficientes que las búsquedas en tablas, que los criterios de transición de estado son más explícitos que en formato tabular y que es más fácil agregar acciones que acompañen a las transiciones de estado. Sin embargo, introduce un nuevo problema: la cantidad de clases hace que el código sea menos compacto que los otros enfoques. El programa que utiliza el patrón de diseño de estados podría verse así:

#incluir <ctype.h> #incluir <stdio.h> 
 

clase StateMachine ; 


clase Estado { público : virtual void feedChar ( StateMachine * , int ) const = 0 ; };  
  
          



clase Antes : público Estado { público : estático Estado const * instanciar (); virtual void feedChar ( StateMachine * , int ) const anular ;    
  
       
         

  protegido : 
Antes () = predeterminado ;      

  privado : 
estado estático const * _instance ; };       



clase Inside : public State { public : static State const * instanciar (); virtual void feedChar ( StateMachine * , int ) const anular ;    
  
       
         

  protegido : 
Dentro () = predeterminado ;      

  privado : 
estado estático const * _instance ; };       



clase Después : público Estado { público : estático Estado const * instanciar (); virtual void feedChar ( StateMachine * , int ) const anular ;    
  
       
         

  protegido : 
Después de () = predeterminado ;      

  privado : 
estado estático const * _instance ; };       



clase StateMachine { público : StateMachine (); void feedChar ( int );  
  
    
     

  protegido : 
void setState ( Estado const * );      

  privado : 
Estado const * _state ; clase amiga Antes ; clase amiga Dentro ; clase amiga Después ; };      
      
      
      



Estado const * Antes :: instanciar () { if ( ! _instance ) { _instance = new Antes ; }   
    
       
  

  devolver _instancia ; } 



void Antes :: feedChar ( StateMachine * const m , int const c ) const { if ( ! isspace ( c )) { putchar ( c ); m -> setState ( Dentro :: instanciar ()); } }        
    
    
    
  



Estado const * Antes :: _instance = nullptr ;    


Estado const * Inside :: instanciar () { if ( ! _instance ) { _instance = new Inside ; }   
    
       
  

  devolver _instancia ; } 



void Inside :: feedChar ( StateMachine * constm , intconstc ) const { if ( c == '\n' ) { putchar ( c ) ; m- > setState ( Antes :: instanciar ( )); } de lo contrario if ( isspace ( c )) { m- > setState ( Después :: instanciar ()); } de lo contrario { putchar ( c ); } }        
      
    
    
      
    
    
    
  



Estado const * Interior :: _instance = nullptr ;    


Estado const * Después :: instanciar () { if ( ! _instance ) { _instance = new Después ; }   
    
       
  

  devolver _instancia ; } 



vacío Después de :: feedChar ( StateMachine * const m , int const c ) const { if ( c == '\n' ) { putchar ( c ); m -> setState ( Antes de :: instanciar ()); } }        
      
    
    
  



Estado const * Después :: _instance = nullptr ;    


StateMachine :: StateMachine () : _state ( Antes :: instanciar ()) {}  


void StateMachine :: feedChar ( int const c ) { _state -> feedChar ( this , c ); }    
   



void StateMachine :: setState ( State const * const s ) { _state = s ; }     
    



int main () { int c ; Máquina de estados m ;  
   
   

  mientras (( c = getchar ()) != EOF ) { m . feedChar ( c ); }      
    
  

  devuelve 0 ; } 

De hecho, la programación basada en autómatas coincide estrechamente con las necesidades de programación que se encuentran en el campo de la automatización .

Un ciclo de producción se modela comúnmente como:

• una secuencia de etapas que avanzan según los datos de entrada (de los captores);
• un conjunto de acciones realizadas dependiendo de la etapa actual.

Varios lenguajes de programación dedicados permiten expresar dicho modelo de formas más o menos sofisticadas.

El ejemplo presentado arriba podría expresarse según este punto de vista como en el siguiente pseudocódigo ('set' activa una variable lógica, 'reset' desactiva una variable lógica, ':' asigna una variable y '=' prueba la igualdad):

nueva línea: '\n'
espacios en blanco: ('\t', '\n', '\v', '\f', '\r', ' ')
estados: (antes, dentro, después)


establecerEstado(c) {
  si antes y (c != nueva línea y c no está en espacio en blanco) entonces se establece dentro
  si está dentro entonces (si c está en un espacio en blanco entonces se establece después de lo contrario si c = nueva línea entonces se establece antes)
  Si después y c = nueva línea entonces se establece antes
}


hacerAcción(c) {
  Si antes y (c != nueva línea y c no está en espacio en blanco) entonces escribe (c)
  Si dentro de y c no hay espacio en blanco entonces escribe (c)
  Si después de y c = nueva línea entonces escribe (c)
}


ciclo {
  anteponer

  bucle hasta que (c: readCharacter) = EOL {
    establecerEstado(c)
    hacerAcción(c)
  }
}

La separación de las rutinas que expresan la progresión del ciclo por un lado, y la acción real por el otro (coincidencia de entrada y salida) permite un código más claro y simple.

En el campo de la automatización, el paso de un paso a otro depende de los datos de entrada que provienen de la propia máquina. Esto se representa en el programa mediante la lectura de caracteres de un texto. En realidad, esos datos informan sobre la posición, la velocidad, la temperatura, etc. de los elementos críticos de una máquina.

Al igual que en la programación GUI , los cambios en el estado de la máquina pueden considerarse como eventos que provocan el paso de un estado a otro, hasta llegar al último. La combinación de estados posibles puede generar una amplia variedad de eventos, definiendo así un ciclo de producción más complejo. En consecuencia, los ciclos suelen estar lejos de ser simples secuencias lineales. Suelen existir ramas paralelas que se ejecutan juntas y alternativas seleccionadas en función de diferentes eventos, que se representan esquemáticamente a continuación:

   s:etapa c:condición
   
   s1
   |
   |-c2
   |
   s2
   |
   ----------
   | |
   |-c31 |-c32
   | |
  s31 s32
   | |
   |-c41 |-c42
   | |
   ----------
   |
   s4

La programación basada en autómatas se utiliza ampliamente en análisis léxicos y sintácticos . ^[1]

Además de eso, pensar en términos de autómatas (es decir, dividir el proceso de ejecución en pasos de autómata y pasar información de un paso a otro a través del estado explícito del autómata ) es necesario para la programación basada en eventos como la única alternativa al uso de procesos o subprocesos paralelos.

Los conceptos de estados y máquinas de estados se utilizan a menudo en el campo de la especificación formal . Por ejemplo, el desarrollo de arquitecturas de software basadas en UML utiliza diagramas de estados para especificar el comportamiento del programa. Asimismo, diversos protocolos de comunicación se especifican a menudo utilizando el concepto explícito de estado (por ejemplo, RFC  793).

El pensamiento en términos de autómatas (pasos y estados) también se puede utilizar para describir la semántica de algunos lenguajes de programación . Por ejemplo, la ejecución de un programa escrito en el lenguaje Refal se describe como una secuencia de pasos de una denominada máquina Refal abstracta; el estado de la máquina es una vista (una expresión arbitraria de Refal sin variables).

Las continuaciones en el lenguaje Scheme requieren pensar en términos de pasos y estados, aunque Scheme en sí no está relacionado de ninguna manera con los autómatas (es recursivo). Para que la característica de llamada/cc funcione, la implementación debe poder capturar un estado completo del programa en ejecución, lo que solo es posible cuando no hay una parte implícita en el estado. Ese estado capturado es lo que se llama continuación y puede considerarse como el estado de un autómata (relativamente complicado). El paso del autómata es deducir la siguiente continuación a partir de la anterior, y el proceso de ejecución es el ciclo de esos pasos.

Alexander Ollongren en su libro ^[2] explica el llamado método de Viena para la descripción semántica de lenguajes de programación, que se basa completamente en autómatas formales.

El sistema STAT [1] es un buen ejemplo del uso del enfoque basado en autómatas; este sistema, además de otras características, incluye un lenguaje integrado llamado STATL que está puramente orientado a autómatas.

Las técnicas basadas en autómatas se han utilizado ampliamente en los dominios donde existen algoritmos basados ​​en la teoría de autómatas, como los análisis de lenguaje formal. ^[1]

Uno de los primeros artículos sobre este tema es el de Johnson et al., 1968. ^[3]

Una de las primeras menciones de la programación basada en autómatas como técnica general se encuentra en el artículo de Peter Naur , 1963. ^[4] El autor llama a la técnica " enfoque de máquina de Turing" , sin embargo no se proporciona ninguna máquina de Turing real en el artículo; en su lugar, se describe la técnica basada en pasos y estados.

La noción de estado no es propiedad exclusiva de la programación basada en autómatas. ^[5] En términos generales, el estado (o estado del programa ) aparece durante la ejecución de cualquier programa informático , como una combinación de toda la información que puede cambiar durante la ejecución. Por ejemplo, un estado de un programa imperativo tradicional consta de

• valores de todas las variables y la información almacenada en la memoria dinámica;
• valores almacenados en registros;
• contenido de la pila (incluidos los valores de las variables locales y las direcciones de retorno);
• valor actual del puntero de instrucción .

Estos se pueden dividir en la parte explícita (como los valores almacenados en variables) y la parte implícita (direcciones de retorno y el puntero de instrucciones).

Dicho esto, un programa basado en autómatas puede considerarse como un caso especial de un programa imperativo, en el que se minimiza la parte implícita del estado. El estado de todo el programa tomado en los dos momentos distintos de entrada en la sección del código de paso puede diferir solo en el estado del autómata. Esto simplifica el análisis del programa.

En la teoría de la programación orientada a objetos , se dice que un objeto tiene un estado interno y es capaz de recibir mensajes , responder a ellos, enviar mensajes a otros objetos y cambiar su estado interno durante el procesamiento de mensajes. En términos más prácticos, llamar al método de un objeto se considera lo mismo que enviar un mensaje al objeto .

Así, por un lado, los objetos de la programación orientada a objetos pueden considerarse como autómatas (o modelos de autómatas) cuyo estado es la combinación de campos privados, y uno o más métodos se consideran el paso . Dichos métodos no deben llamarse entre sí ni a sí mismos, ni directa ni indirectamente, de lo contrario el objeto no puede considerarse implementado de manera autómata.

Por otro lado, el objeto es bueno para implementar un modelo de un autómata. Cuando se utiliza el enfoque basado en autómatas dentro de un lenguaje orientado a objetos, un modelo de autómata generalmente se implementa mediante una clase, el estado se representa con campos privados de la clase y el paso se implementa como un método; dicho método suele ser el único método público no constante de la clase (además de los constructores y destructores). Otros métodos públicos podrían consultar el estado pero no cambiarlo. Todos los métodos secundarios (como los manejadores de estados particulares) generalmente están ocultos dentro de la parte privada de la clase.

• Autómata celular
• Programación no determinista
• Patrón de estado
• Esterel , un lenguaje basado en autómatas
• Umple , una herramienta para añadir autómatas a Java y C++

• JV Noble. «Máquinas de estados finitos en Forth» — programación basada en autómatas en Forth
• Harel, David (1987). "Diagramas de estados: un formalismo visual para sistemas complejos" (PDF) . Sci. Comput. Programming . 8 (3): 231–274. doi : 10.1016/0167-6423(87)90035-9 .
• Harel, David; Drusinsky, D. (1989). "Uso de diagramas de estado para la descripción y síntesis de hardware". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 8 (7): 798–807. doi :10.1109/43.31537. S2CID  8754800.
• Polikarpova NI, Shalyto AA Programación basada en autómatas SPb.: Piter. 2009 (ruso)
• Universidad ITMO, Departamento de "Tecnología de Programación"