El análisis de estados de tipo , a veces llamado análisis de protocolo , es una forma de análisis de programas que se emplea en los lenguajes de programación . Se aplica más comúnmente a los lenguajes orientados a objetos . Los estados de tipo definen secuencias válidas de operaciones que se pueden realizar en una instancia de un tipo determinado. Los estados de tipo, como sugiere el nombre, asocian información de estado con variables de ese tipo. Esta información de estado se utiliza para determinar en tiempo de compilación qué operaciones son válidas para ser invocadas en una instancia del tipo. Las operaciones realizadas en un objeto que normalmente solo se ejecutarían en tiempo de ejecución se realizan sobre la información de estado de tipo que se modifica para que sea compatible con el nuevo estado del objeto.
Los estados de tipo son capaces de representar refinamientos de tipo de comportamiento como "el método A debe ser invocado antes de que se invoque el método B , y el método C no puede ser invocado entre medio". Los estados de tipo son adecuados para representar recursos que utilizan semántica de apertura/cierre al imponer secuencias semánticamente válidas como "abrir y luego cerrar" en lugar de secuencias no válidas como dejar un archivo en un estado abierto. Dichos recursos incluyen elementos del sistema de archivos, transacciones, conexiones y protocolos. Por ejemplo, los desarrolladores pueden querer especificar que los archivos o sockets deben abrirse antes de leerse o escribirse, y que ya no se pueden leer o escribir si se han cerrado. El nombre "estado de tipo" proviene del hecho de que este tipo de análisis a menudo modela cada tipo de objeto como una máquina de estados finitos . En esta máquina de estados, cada estado tiene un conjunto bien definido de métodos/mensajes permitidos, y las invocaciones de métodos pueden causar transiciones de estado. Las redes de Petri también se han propuesto como un posible modelo de comportamiento para su uso con tipos de refinamiento . [1]
El análisis de estado de tipo fue introducido por Rob Strom en 1983 [2] en el lenguaje de implementación de red (NIL) desarrollado en el Laboratorio Watson de IBM . Fue formalizado por Strom y Yemini en un artículo de 1986 [3] que describía cómo usar el estado de tipo para rastrear el grado de inicialización de las variables, garantizando que las operaciones nunca se aplicarían en datos inicializados incorrectamente, y fue generalizado en el lenguaje de programación Hermes .
En los últimos años, varios estudios han desarrollado formas de aplicar el concepto de estado de tipo a los lenguajes orientados a objetos. [4] [5]
struct{int x;int y;int z;}. Strom y Yemini (1986) exigieron que el conjunto de estados de tipo para un tipo dado estuviera parcialmente ordenado de modo que se pueda obtener un estado de tipo inferior a partir de uno superior descartando alguna información. Por ejemplo, una intvariable en C normalmente tiene los estados de tipo " no inicializado " < " inicializado ", y un FILE*puntero puede tener los estados de tipo " no asignado " < " asignado, pero no inicializado " < " inicializado, pero archivo no abierto " < " archivo abierto ". Además, Strom y Yemini exigen que cada dos estados de tipo tengan un límite inferior máximo, es decir, que el orden parcial sea par un semirretículo de encuentro ; y que cada orden tenga un elemento mínimo, siempre llamado "⊥".
Su análisis se basa en la simplificación de que a cada variable v se le asigna solo un estado de tipo para cada punto en el texto del programa; si se llega a un punto p por dos rutas de ejecución diferentes y v hereda diferentes estados de tipo a través de cada ruta, entonces el estado de tipo de v en p se toma como el límite inferior máximo de los estados de tipo heredados. Por ejemplo, en el siguiente fragmento de código C, la variable nhereda el estado de tipo " initialized " y " uninitialized " de la parte theny la parte (vacía) else, respectivamente, por lo tanto, tiene el estado de tipo " uninitialized " después de toda la declaración condicional.
int n ; // aquí, n tiene typestate "sin inicializar" if (...) { n = 5 ; // aquí, n tiene typestate "sin inicializar" } else { /*no hacer nada*/ // aquí, n tiene typestate "sin inicializar" } // aquí, n tiene typestate "sin inicializar" = biggest_lower_bound("inicializado", "sin inicializar") Cada operación básica [nota 1] debe estar equipada con una transición de estado de tipo , es decir, para cada parámetro, el estado de tipo requerido y garantizado antes y después de la operación, respectivamente. Por ejemplo, una operación fwrite(...,fd)requiere fdtener el estado de tipo " archivo abierto ". Más precisamente, una operación puede tener varios resultados , cada uno de los cuales necesita su propia transición de estado de tipo. Por ejemplo, el código C FILE *fd=fopen("foo","r")establece fdel estado de tipo de en " archivo abierto " y " sin asignar " si la apertura tiene éxito y falla, respectivamente.
Para cada dos estados de tipo t 1 <· t 2 , se debe proporcionar una operación de conversión de estado de tipo única que, cuando se aplica a un objeto de estado de tipo t 2 , reduce su estado de tipo a t 1 , posiblemente liberando algunos recursos. Por ejemplo, fclose(fd)convierte fdel estado de tipo de " archivo abierto " a " inicializado, pero archivo no abierto ".
Se dice que la ejecución de un programa es correcta en cuanto a estado de tipo si
Se dice que un texto de programa es consistente con el estado de tipo si se puede transformar, mediante la adición de coerciones de estado de tipo adecuadas, en un programa cuyos puntos se pueden etiquetar estáticamente con estados de tipo de modo que cualquier camino permitido por el flujo de control sea correcto con el estado de tipo. Strom y Yemini ofrecen un algoritmo de tiempo lineal que verifica la consistencia del estado de tipo de un texto de programa dado y calcula dónde insertar qué operación de coerción, si corresponde.
Para lograr un análisis preciso y efectivo de los estados de los tipos, es necesario abordar el problema del aliasing . El aliasing ocurre cuando un objeto tiene más de una referencia o puntero que lo apunta. Para que el análisis sea correcto, los cambios de estado de un objeto determinado deben reflejarse en todas las referencias que apuntan a ese objeto, pero en general es un problema difícil rastrear todas esas referencias. Esto se vuelve especialmente difícil si el análisis necesita ser modular, es decir, aplicable a cada parte de un programa grande por separado sin tener en cuenta el resto del programa.
Como otro problema, para algunos programas, el método de tomar el límite inferior máximo en las rutas de ejecución convergentes y agregar las operaciones de coerción descendente correspondientes parece ser inadecuado. Por ejemplo, antes del return 1en el siguiente programa, [nota 3] se inicializan todos los componentes x, yy zof coord, pero el enfoque de Strom y Yemini no reconoce esto, ya que cada inicialización de un componente de estructura en el cuerpo del bucle tiene que ser coercionada descendentemente en la reentrada del bucle para cumplir con el estado de tipo de la primera entrada del bucle, es decir, ⊥. Un problema relacionado es que este ejemplo requeriría la sobrecarga de las transiciones de estado de tipo; por ejemplo, parse_int_attr("x",&coord->x)cambia un estado de tipo " ningún componente inicializado " a " componente x inicializado ", pero también " componente y inicializado " a " componente x e y inicializados ".
int parse_coord ( struct { intx ; inty ; intz ; } * coord ) { intseed = 0 ; /* recordar qué atributos han sido analizados * / mientras ( 1 ) si ( parse_int_attr ( "x" , & coord -> x )) visto |= 1 ; de lo contrario si ( parse_int_attr ( "y" , & coord -> y )) visto |= 2 ; de lo contrario si ( parse_int_attr ( "z" , & coord -> z )) visto |= 4 ; de lo contrario romper ; if ( seen != 7 ) /* falta algún atributo, falla */ return 0 ; ... /* todos los atributos presentes, realiza algunos cálculos y tiene éxito */ return 1 ; } Existen varios enfoques que buscan inferir estados de tipos a partir de programas (o incluso otros artefactos como contratos). Muchos de ellos pueden inferir estados de tipos en tiempo de compilación [6] [7] [8] [9] y otros extraen los modelos dinámicamente. [10] [11] [12] [13] [14] [15]
Typestate es un concepto experimental que aún no ha trascendido a los lenguajes de programación convencionales. Sin embargo, muchos proyectos académicos investigan activamente cómo hacerlo más útil como técnica de programación cotidiana. Dos ejemplos son los lenguajes Plaid y Obsidian, que están siendo desarrollados por el grupo de Jonathan Aldrich en la Universidad Carnegie Mellon . [16] [17] Otros ejemplos incluyen el marco de investigación del lenguaje Clara [18] , versiones anteriores del lenguaje Rust y la >>palabra clave en ATS . [19]
+=en C, y rutinas de biblioteca estándar, por ejemplofopen()mallocse haya freeutilizado toda la memoria ed. En la mayoría de los lenguajes de programación, la vida útil de una variable puede terminar antes de la finalización del programa; por lo tanto, la noción de corrección del estado de tipo debe afinarse en consecuencia.int parse_int_attr(const char *name,int *val)se inicializa *valsiempre que tiene éxito