Sistema de tipos

Compartir Imprimir Citar

En los lenguajes de programación, un sistema de tipos es un sistema lógico que comprende un conjunto de reglas que asigna una propiedad llamada tipo a las diversas construcciones de un programa de computadora, como variables, expresiones, funciones o módulos. Estos tipos formalizan y hacen cumplir las categorías implícitas que el programador utiliza para tipos de datos algebraicos, estructuras de datos u otros componentes (p. ej., "cadena", "matriz de flotantes", "función que devuelve booleanos"). El propósito principal de un sistema de tipos es reducir las posibilidades de errores en los programas de computadora.definiendo interfaces entre diferentes partes de un programa de computadora y luego verificando que las partes se hayan conectado de manera consistente. Esta verificación puede ocurrir de forma estática (en tiempo de compilación), dinámicamente (en tiempo de ejecución) o como una combinación de ambas. Los sistemas de tipos también tienen otros propósitos, como expresar reglas comerciales, permitir ciertas optimizaciones del compilador, permitir el envío múltiple, proporcionar una forma de documentación, etc.

Un sistema de tipos asocia un tipo con cada valor calculado y, al examinar el flujo de estos valores, intenta garantizar o probar que no pueden ocurrir errores de tipo. El sistema de tipo dado en cuestión determina qué constituye un error de tipo, pero en general, el objetivo es evitar que las operaciones que esperan un cierto tipo de valor se utilicen con valores para los que esa operación no tiene sentido (errores de validez). Los sistemas de tipos a menudo se especifican como parte de los lenguajes de programación y se integran en intérpretes y compiladores, aunque el sistema de tipos de un lenguaje se puede ampliar con herramientas opcionales que realizan comprobaciones adicionales utilizando la sintaxis y la gramática de tipos originales del lenguaje.

Resumen de uso

Un ejemplo de un sistema de tipo simple es el del lenguaje C. Las partes de un programa en C son las definiciones de funciones. Una función es invocada por otra función. La interfaz de una función establece el nombre de la función y una lista de parámetros que se pasan al código de la función. El código de una función de invocación establece el nombre de la función invocada, junto con los nombres de las variables que contienen valores para pasarle. Durante la ejecución, los valores se colocan en el almacenamiento temporal, luego la ejecución salta al código de la función invocada. El código de la función invocada accede a los valores y hace uso de ellos. Si las instrucciones dentro de la función se escriben con la suposición de recibir un valor entero, pero el código de llamada pasó un valor de punto flotante, entonces la función invocada calculará el resultado incorrecto. El compilador de C comprueba los tipos de los argumentos pasados ​​a una función cuando se llama contra los tipos de los parámetros declarados en la definición de la función. Si los tipos no coinciden, el compilador genera un error en tiempo de compilación.

Un compilador también puede usar el tipo estático de un valor para optimizar el almacenamiento que necesita y la elección de algoritmos para operaciones en el valor. En muchos compiladores de C, el tipo de datos flotante, por ejemplo, se representa en 32 bits, de acuerdo con la especificación IEEE para números de coma flotante de precisión simple. Por lo tanto, utilizarán operaciones de microprocesador específicas de punto flotante en esos valores (suma de punto flotante, multiplicación, etc.).

La profundidad de las restricciones de tipo y la forma de su evaluación afectan la tipificación del lenguaje. Un lenguaje de programación puede además asociar una operación con varias resoluciones para cada tipo, en el caso del polimorfismo de tipos. La teoría de tipos es el estudio de los sistemas de tipos. Los tipos concretos de algunos lenguajes de programación, como enteros y cadenas, dependen de aspectos prácticos de la arquitectura de la computadora, la implementación del compilador y el diseño del lenguaje.

Fundamentos

Formalmente, la teoría de tipos estudia los sistemas de tipos. Un lenguaje de programación debe tener la oportunidad de verificar tipos utilizando el sistema de tipos, ya sea en tiempo de compilación o en tiempo de ejecución, anotado manualmente o inferido automáticamente. Como Mark Manasse lo expresó de manera concisa:

El problema fundamental que aborda una teoría de tipos es garantizar que los programas tengan significado. El problema fundamental causado por una teoría de tipos es que los programas significativos pueden no tener significados atribuidos a ellos. La búsqueda de sistemas de tipos más ricos resulta de esta tensión.

La asignación de un tipo de datos, denominado tipeo, da significado a una secuencia de bits, como un valor en la memoria o algún objeto, como una variable. El hardware de una computadora de propósito general no puede discriminar entre, por ejemplo, una dirección de memoria y un código de instrucción, o entre un carácter, un número entero o un número de punto flotante, porque no hace distinción intrínseca entre cualquiera de los valores posibles que una secuencia de bits podría significar. Asociar una secuencia de bits con un tipo transmite ese significado al hardware programable para formar un sistema simbólico compuesto por ese hardware y algún programa.

Un programa asocia cada valor con al menos un tipo específico, pero también puede ocurrir que un valor esté asociado con muchos subtipos. Otras entidades, como objetos, módulos, canales de comunicación y dependencias pueden asociarse con un tipo. Incluso un tipo puede asociarse con un tipo. En teoría, una implementación de un sistema de tipos podría asociar identificaciones denominadas tipo de datos (un tipo de valor), clase (un tipo de objeto) y tipo (un tipo de un tipo o metatipo). Estas son las abstracciones por las que puede pasar la escritura, en una jerarquía de niveles contenidos en un sistema.

Cuando un lenguaje de programación desarrolla un sistema de tipos más elaborado, obtiene un conjunto de reglas más detalladas que la verificación de tipos básica, pero esto tiene un precio cuando las inferencias de tipos (y otras propiedades) se vuelven indecidibles, y cuando se debe prestar más atención por parte de los usuarios. el programador para anotar el código o para considerar las operaciones y el funcionamiento relacionados con la computadora. Es un desafío encontrar un sistema de tipos lo suficientemente expresivo que satisfaga todas las prácticas de programación de una manera segura.

Cuantas más restricciones de tipo impone el compilador, más fuertemente tipado es un lenguaje de programación. Los lenguajes fuertemente tipados a menudo requieren que el programador realice conversiones explícitas en contextos donde una conversión implícita no causaría daño. El sistema de tipos de Pascal se ha descrito como "demasiado fuerte" porque, por ejemplo, el tamaño de una matriz o cadena es parte de su tipo, lo que dificulta algunas tareas de programación. Haskell también está fuertemente tipado, pero sus tipos se infieren automáticamente, por lo que las conversiones explícitas a menudo son innecesarias.

Un compilador de lenguaje de programación también puede implementar un tipo dependiente o un sistema de efectos, lo que permite que un verificador de tipos verifique aún más especificaciones del programa. Más allá de simples pares de tipo de valor, una "región" virtual de código está asociada con un componente de "efecto" que describe qué se está haciendo con qué y permite, por ejemplo, "lanzar" un informe de error. Por lo tanto, el sistema simbólico puede ser un sistema de tipo y efecto, lo que le otorga más verificación de seguridad que la verificación de tipo sola.

Ya sea automatizado por el compilador o especificado por un programador, un sistema de tipos hace que el comportamiento del programa sea ilegal si está fuera de las reglas del sistema de tipos. Las ventajas proporcionadas por los sistemas de tipo especificado por el programador incluyen:

Las ventajas proporcionadas por los sistemas de tipos especificados por el compilador incluyen:

Escriba errores

Un error de tipo es una condición no deseada que puede manifestarse en varias etapas del desarrollo de un programa. Por lo tanto, se necesita una facilidad para la detección del error en el sistema de tipos. En algunos lenguajes, como Haskell, para los cuales la inferencia de tipos está automatizada, lint podría estar disponible para su compilador para ayudar en la detección de errores.

La seguridad de tipos contribuye a la corrección del programa, pero solo puede garantizar la corrección a costa de hacer que la verificación de tipos en sí misma sea un problema indecidible. En un sistema de tipos con verificación automática de tipos, un programa puede ejecutarse incorrectamente pero no producir errores de compilación. La división por cero es una operación insegura e incorrecta, pero un verificador de tipo que se ejecuta solo en tiempo de compilación no busca la división por cero en la mayoría de los idiomas, y luego se deja como un error de tiempo de ejecución. Para probar la ausencia de estos defectos, son de uso común otros tipos de métodos formales, conocidos colectivamente como análisis de programas. Alternativamente, un sistema de tipo lo suficientemente expresivo, como en lenguajes de tipo dependiente, puede prevenir este tipo de errores (por ejemplo, expresar el tipo de números distintos de cero). Además, las pruebas de software son un método empírico para encontrar errores que el verificador de tipos no puede detectar.

Comprobación de tipos

El proceso de verificar y hacer cumplir las restricciones de tipos (verificación de tipos) puede ocurrir en tiempo de compilación (una verificación estática) o en tiempo de ejecución. Si una especificación de lenguaje requiere sus reglas de escritura fuertemente (es decir, más o menos permitiendo solo aquellas conversiones de tipo automáticas que no pierden información), uno puede referirse al proceso como fuertemente tipado, si no, como débilmente tipeado. Los términos no suelen utilizarse en un sentido estricto.

Comprobación de tipo estático

La verificación de tipo estático es el proceso de verificar la seguridad de tipo de un programa basado en el análisis del texto de un programa (código fuente). Si un programa pasa un verificador de tipo estático, se garantiza que el programa satisfará algún conjunto de propiedades de seguridad de tipo para todas las entradas posibles.

La verificación de tipos estáticos puede considerarse una forma limitada de verificación de programas (ver seguridad de tipos) y, en un lenguaje seguro de tipos, también puede considerarse una optimización. Si un compilador puede probar que un programa está bien escrito, entonces no necesita emitir comprobaciones de seguridad dinámicas, lo que permite que el binario compilado resultante se ejecute más rápido y sea más pequeño.

La verificación de tipos estáticos para lenguajes completos de Turing es inherentemente conservadora. Es decir, si un sistema de tipos es sólido (lo que significa que rechaza todos los programas incorrectos) y decidible (lo que significa que es posible escribir un algoritmo que determine si un programa está bien tipificado), entonces debe ser incompleto (lo que significa que hay son programas correctos, que también son rechazados, aunque no encuentren errores de tiempo de ejecución). Por ejemplo, considere un programa que contenga el código:if <complex test> then <do something> else <signal that there is a type error>

Incluso si la expresión <complex test>siempre se evalúa trueen tiempo de ejecución, la mayoría de los verificadores de tipo rechazarán el programa como mal tipificado, porque es difícil (si no imposible) para un analizador estático determinar que la elsebifurcación no se tomará. En consecuencia, un verificador de tipo estático detectará rápidamente los errores de tipo en las rutas de código que se usan con poca frecuencia. Sin la verificación de tipo estático, incluso las pruebas de cobertura de código con una cobertura del 100 % pueden no encontrar tales errores de tipo. Es posible que las pruebas no detecten este tipo de errores, ya que se debe tener en cuenta la combinación de todos los lugares donde se crean los valores y todos los lugares donde se utiliza un determinado valor.

Una serie de características útiles y comunes del lenguaje de programación no se pueden verificar de forma estática, como el downcasting. Por lo tanto, muchos lenguajes tendrán verificación de tipos tanto estática como dinámica; el verificador de tipo estático verifica lo que puede y las verificaciones dinámicas verifican el resto.

Muchos lenguajes con verificación de tipo estático proporcionan una forma de omitir el verificador de tipo. Algunos lenguajes permiten a los programadores elegir entre seguridad de tipo estático y dinámico. Por ejemplo, C# distingue entre variables de tipo estático y de tipo dinámico. Los usos del primero se verifican estáticamente, mientras que los usos del segundo se verifican dinámicamente. Otros lenguajes permiten escribir código que no es de tipo seguro; por ejemplo, en C, los programadores pueden emitir libremente un valor entre dos tipos que tengan el mismo tamaño, subvirtiendo efectivamente el concepto de tipo.

Para obtener una lista de idiomas con verificación de tipos estáticos, consulte la categoría de idiomas con tipos estáticos.

Comprobación de tipo dinámico e información de tipo de tiempo de ejecución

La verificación dinámica de tipos es el proceso de verificar la seguridad de tipos de un programa en tiempo de ejecución. Las implementaciones de lenguajes con verificación de tipo dinámica generalmente asocian cada objeto de tiempo de ejecución con una etiqueta de tipo (es decir, una referencia a un tipo) que contiene su información de tipo. Esta información de tipo de tiempo de ejecución (RTTI) también se puede utilizar para implementar envío dinámico, enlace tardío, downcasting, reflexión y características similares.

La mayoría de los lenguajes con seguridad de tipos incluyen alguna forma de verificación dinámica de tipos, incluso si también tienen un verificador de tipos estático. La razón de esto es que muchas características o propiedades útiles son difíciles o imposibles de verificar estáticamente. Por ejemplo, suponga que un programa define dos tipos, A y B, donde B es un subtipo de A. Si el programa intenta convertir un valor de tipo A en tipo B, lo que se conoce como conversión descendente, entonces la operación solo es legal. si el valor que se está convirtiendo es en realidad un valor de tipo B. Por lo tanto, se necesita una verificación dinámica para verificar que la operación es segura. Este requisito es una de las críticas al downcasting.

Por definición, la comprobación dinámica de tipos puede hacer que un programa falle en tiempo de ejecución. En algunos lenguajes de programación, es posible anticipar y recuperarse de estas fallas. En otros, los errores de verificación de tipo se consideran fatales.

Los lenguajes de programación que incluyen verificación de tipos dinámicos pero no verificación de tipos estáticos a menudo se denominan "lenguajes de programación de tipos dinámicos". Para obtener una lista de dichos lenguajes, consulte la categoría de lenguajes de programación de tipo dinámico.

Combinación de verificación de tipo estática y dinámica

Algunos idiomas permiten la escritura tanto estática como dinámica. Por ejemplo, Java y algunos otros lenguajes ostensiblemente tipificados estáticamente admiten la conversión de tipos a sus subtipos, consultando un objeto para descubrir su tipo dinámico y otras operaciones de tipo que dependen de la información de tipo en tiempo de ejecución. Otro ejemplo es C++ RTTI. En términos más generales, la mayoría de los lenguajes de programación incluyen mecanismos para enviar diferentes "tipos" de datos, como uniones disjuntas, polimorfismo en tiempo de ejecución y tipos de variantes. Incluso cuando no interactúan con las anotaciones de tipo o la verificación de tipo, estos mecanismos son materialmente similares a las implementaciones de escritura dinámica. Consulte el lenguaje de programación para obtener más información sobre las interacciones entre la tipificación estática y dinámica.

A los objetos en lenguajes orientados a objetos generalmente se accede mediante una referencia cuyo tipo de destino estático (o tipo de manifiesto) es igual al tipo de tiempo de ejecución del objeto (su tipo latente) o un supertipo del mismo. Esto es conforme con el principio de sustitución de Liskov, que establece que todas las operaciones realizadas en una instancia de un tipo determinado también se pueden realizar en una instancia de un subtipo. Este concepto también se conoce como subsunción o polimorfismo de subtipo. En algunos idiomas, los subtipos también pueden poseer tipos de retorno y tipos de argumento covariantes o contravariantes, respectivamente.

Ciertos lenguajes, por ejemplo, Clojure, Common Lisp o Cython, se verifican de forma dinámica de forma predeterminada, pero permiten que los programas opten por la verificación de tipo estático al proporcionar anotaciones opcionales. Una razón para usar estas sugerencias sería optimizar el rendimiento de las secciones críticas de un programa. Esto se formaliza mediante tipificación gradual. El entorno de programación DrRacket, un entorno pedagógico basado en Lisp y precursor del lenguaje Racket, también es de tipo suave.

Por el contrario, a partir de la versión 4.0, el lenguaje C# proporciona una forma de indicar que una variable no debe verificarse estáticamente. Una variable cuyo tipo es dynamicno estará sujeta a la verificación de tipo estático. En cambio, el programa se basa en la información del tipo de tiempo de ejecución para determinar cómo se puede usar la variable.

En Rust, el tipo proporciona escritura dinámica de tipos.std::any'static

Comprobación estática y dinámica de tipos en la práctica

La elección entre escritura estática y dinámica requiere ciertas compensaciones.

La escritura estática puede encontrar errores de tipo de manera confiable en el momento de la compilación, lo que aumenta la confiabilidad del programa entregado. Sin embargo, los programadores no están de acuerdo sobre la frecuencia con la que ocurren los errores tipográficos, lo que genera más desacuerdos sobre la proporción de esos errores codificados que se detectarían al representar adecuadamente los tipos diseñados en el código. Los defensores de la escritura estática creen que los programas son más confiables cuando se han verificado correctamente, mientras que los defensores de la escritura dinámica apuntan al código distribuido que ha demostrado ser confiable y a las pequeñas bases de datos de errores. El valor de la escritura estática aumenta a medida que aumenta la fuerza del sistema de tipos. defensores de la tipificación dependiente,implementado en lenguajes como Dependent ML y Epigram, han sugerido que casi todos los errores pueden considerarse errores de tipo, si los tipos utilizados en un programa son declarados correctamente por el programador o inferidos correctamente por el compilador.

La escritura estática generalmente da como resultado un código compilado que se ejecuta más rápido. Cuando el compilador conoce los tipos de datos exactos que están en uso (lo cual es necesario para la verificación estática, ya sea mediante declaración o inferencia), puede producir un código de máquina optimizado. Algunos lenguajes de tipado dinámico, como Common Lisp, permiten declaraciones de tipo opcionales para la optimización por este motivo.

Por el contrario, la escritura dinámica puede permitir que los compiladores se ejecuten más rápido y que los intérpretes carguen código nuevo de forma dinámica, porque los cambios en el código fuente en lenguajes de escritura dinámica pueden dar como resultado menos comprobaciones para realizar y menos código para revisar. Esto también puede reducir el ciclo de edición-compilación-prueba-depuración.

Los lenguajes de tipos estáticos que carecen de inferencia de tipos (como C y Java antes de la versión 10) requieren que los programadores declaren los tipos que debe usar un método o función. Esto puede servir como documentación adicional del programa, que es activa y dinámica, en lugar de estática. Esto permite que un compilador evite que se desvíe de la sincronía y que los programadores lo ignoren. Sin embargo, un idioma se puede escribir de forma estática sin necesidad de declaraciones de tipo (los ejemplos incluyen Haskell, Scala, OCaml, F# y, en menor medida, C# y C++), por lo que la declaración de tipo explícita no es un requisito necesario para la escritura estática en todos los idiomas.

La tipificación dinámica permite construcciones que algunas (simples) comprobaciones de tipos estáticos rechazarían como ilegales. Por ejemplo, las funciones eval, que ejecutan datos arbitrarios como código, se vuelven posibles. Una función eval es posible con escritura estática, pero requiere usos avanzados de tipos de datos algebraicos. Además, la escritura dinámica se adapta mejor al código de transición y la creación de prototipos, como permitir que una estructura de datos de marcador de posición (objeto simulado) se use de forma transparente en lugar de una estructura de datos completa (generalmente con fines de experimentación y prueba).

La escritura dinámica generalmente permite la escritura pato (lo que facilita la reutilización del código). Muchos lenguajes con escritura estática también cuentan con escritura de pato u otros mecanismos como programación genérica que también permiten una reutilización de código más fácil.

La escritura dinámica generalmente hace que la metaprogramación sea más fácil de usar. Por ejemplo, las plantillas de C++ suelen ser más engorrosas de escribir que el código equivalente de Ruby o Python, ya que C++ tiene reglas más estrictas con respecto a las definiciones de tipo (tanto para funciones como para variables). Esto obliga a un desarrollador a escribir más código repetitivo para una plantilla de lo que necesitaría un desarrollador de Python. Las construcciones de tiempo de ejecución más avanzadas, como las metaclases y la introspección, suelen ser más difíciles de usar en lenguajes de tipos estáticos. En algunos idiomas, estas funciones también se pueden usar, por ejemplo, para generar nuevos tipos y comportamientos sobre la marcha, en función de los datos de tiempo de ejecución. Tales construcciones avanzadas a menudo son proporcionadas por lenguajes de programación dinámicos; muchos de estos están tipificados dinámicamente, aunque la tipificación dinámica no necesita estar relacionada conLenguajes de programación dinámicos.

Sistemas de tipo fuerte y débil.

Los idiomas a menudo se denominan coloquialmente tipificados fuertemente o tipificados débilmente. De hecho, no existe una definición universalmente aceptada de lo que significan estos términos. En general, existen términos más precisos para representar las diferencias entre los sistemas de tipos que llevan a las personas a llamarlos "fuertes" o "débiles".

Escriba la seguridad y la seguridad de la memoria

Una tercera forma de categorizar el sistema de tipos de un lenguaje de programación es por la seguridad de las operaciones y conversiones tipificadas. Los informáticos utilizan el término lenguaje seguro para tipos para describir lenguajes que no permiten operaciones o conversiones que violen las reglas del sistema de tipos.

Los informáticos utilizan el término lenguaje seguro para la memoria (o simplemente lenguaje seguro) para describir lenguajes que no permiten que los programas accedan a la memoria que no ha sido asignada para su uso. Por ejemplo, un lenguaje seguro para la memoria verificará los límites de la matriz o garantizará estáticamente (es decir, en el momento de la compilación antes de la ejecución) que los accesos a la matriz fuera de los límites de la matriz provocarán errores en el tiempo de compilación y quizás en el tiempo de ejecución.

Considere el siguiente programa de un lenguaje que es seguro tanto para tipos como para memoria:

var x:= 5;   
var y:= "37";
var z:= x + y;

En este ejemplo, la variable ztendrá el valor 42. Aunque esto puede no ser lo que anticipó el programador, es un resultado bien definido. Si yfuera una cadena diferente, una que no pudiera convertirse en un número (por ejemplo, "Hola mundo"), el resultado también estaría bien definido. Tenga en cuenta que un programa puede tener seguridad de tipos o de memoria y aun así fallar en una operación no válida. Esto es para lenguajes donde el sistema de tipos no es lo suficientemente avanzado para especificar con precisión la validez de las operaciones en todos los operandos posibles. Pero si un programa encuentra una operación que no es segura, la única opción suele ser finalizar el programa.

Ahora considere un ejemplo similar en C:

int x = 5;   
char y [] = "37";   
carácter * z = x + y;     
printf ("%c n ", * z); 

En este ejemplo, apuntará a una dirección de memoria cinco caracteres más allá de, equivalente a tres caracteres después del carácter cero final de la cadena a la que apunta. Esta es la memoria a la que no se espera que acceda el programa. Puede contener datos basura, y ciertamente no contiene nada útil. Como muestra este ejemplo, C no es un lenguaje seguro para la memoria ni para los tipos. zyy

En general, la seguridad de tipo y la seguridad de memoria van de la mano. Por ejemplo, un lenguaje que admita aritmética de punteros y conversiones de números a punteros (como C) no es seguro para la memoria ni para los tipos, porque permite acceder a la memoria arbitraria como si fuera una memoria válida de cualquier tipo.

Para obtener más información, consulte seguridad de la memoria.

Niveles variables de verificación de tipos

Algunos lenguajes permiten que se apliquen diferentes niveles de verificación a diferentes regiones de código. Ejemplos incluyen:

También se pueden utilizar herramientas adicionales como lint e IBM Rational Purify para lograr un mayor nivel de rigor.

Sistemas de tipos opcionales

Se ha propuesto, principalmente por Gilad Bracha, que la elección del sistema de tipo sea independiente de la elección del idioma; que un sistema de tipos debe ser un módulo que se puede conectar a un idioma según sea necesario. Él cree que esto es ventajoso, porque lo que él llama sistemas de tipos obligatorios hace que los lenguajes sean menos expresivos y el código más frágil. El requisito de que el sistema de tipos no afecte la semántica del lenguaje es difícil de cumplir.

La tipificación opcional está relacionada con la tipificación gradual, pero es distinta de ella. Si bien ambas disciplinas de escritura se pueden usar para realizar un análisis estático del código (escritura estática), los sistemas de tipos opcionales no imponen la seguridad de tipos en tiempo de ejecución (escritura dinámica).

Polimorfismo y tipos

El término polimorfismo se refiere a la capacidad del código (especialmente, funciones o clases) para actuar sobre valores de múltiples tipos, o la capacidad de diferentes instancias de la misma estructura de datos para contener elementos de diferentes tipos. Los sistemas de tipos que permiten el polimorfismo generalmente lo hacen para mejorar el potencial de reutilización del código: en un lenguaje con polimorfismo, los programadores solo necesitan implementar una estructura de datos como una lista o una matriz asociativa una vez, en lugar de una vez para cada tipo de elemento con el que piensan utilizarlo. Por esta razón, los informáticos a veces llaman programación genérica al uso de ciertas formas de polimorfismo. Los fundamentos de la teoría de tipos del polimorfismo están estrechamente relacionados con los de la abstracción, la modularidad y (en algunos casos) la subtipificación.

Sistemas de tipos especializados

Se han creado muchos tipos de sistemas que están especializados para su uso en ciertos entornos con ciertos tipos de datos, o para el análisis de programas estáticos fuera de banda. Con frecuencia, estos se basan en ideas de la teoría formal de tipos y solo están disponibles como parte de sistemas de investigación prototipo.

La siguiente tabla ofrece una descripción general de los conceptos teóricos de tipos que se utilizan en los sistemas de tipos especializados. Los nombres M, N, O se extienden sobre los términos y los nombres { estilo de visualización  sigma,  tau}se extienden sobre los tipos. La notación { estilo de visualización  tau [ alfa: =  sigma]}(resp. { estilo de visualización  tau [x: = N]}) describe el tipo que resulta de reemplazar todas las apariciones de la variable tipo α (resp. término variable x) en τ por el tipo σ (resp. término N).

Noción de tipoNotaciónSignificado
Funciónsigma to tauSi M tiene tipo sigma to tauy N tiene tipo σ, entonces la aplicación { estilo de visualización M (N)}tiene tipo τ.
Producto{ estilo de visualización  sigma  tiempos  tau}Si M tiene tipo { estilo de visualización  sigma  tiempos  tau}, entonces { estilo de visualización M = (N, O)}es un par tal que N tiene tipo σ y O tiene tipo τ.
Suma{ estilo de visualización  sigma +  tau}Si M tiene tipo { estilo de visualización  sigma +  tau}, entonces { estilo de visualización M =  iota _ {1} (N)}la primera inyección es tal que N tiene tipo σ, o{ estilo de visualización M =  iota _ {2} (N)}es la segunda inyección tal que N tiene tipo τ.
Intersección{ estilo de visualización  sigma  cap  tau}Si M tiene tipo { estilo de visualización  sigma  cap  tau}, entonces M tiene tipo σ y M tiene tipo τ.
Unión{ estilo de visualización  sigma  taza  tau}Si M tiene tipo { estilo de visualización  sigma  taza  tau}, entonces M tiene tipo σ o M tiene tipo τ.
Registro{ estilo de visualización  langle x:  tau  rangle}Si M tiene tipo { estilo de visualización  langle x:  tau  rangle}, entonces M tiene un miembro x que tiene tipo τ.
Polimórfico{ estilo de visualización  para todos  alfa.  tau}Si M tiene tipo { estilo de visualización  para todos  alfa.  tau}, entonces M tiene tipo { estilo de visualización  tau [ alfa: =  sigma]}para cualquier tipo σ.
existencial{displaystyle existe alpha.tau }Si M tiene tipo {displaystyle existe alpha.tau }, entonces M tiene tipo { estilo de visualización  tau [ alfa: =  sigma]}para algún tipo σ.
recursivo{ estilo de visualización  mu  alfa.  tau}Si M tiene tipo { estilo de visualización  mu  alfa.  tau}, entonces M tiene tipo { estilo de visualización  tau [ alfa: =  mu  alfa.  tau]}.
función dependiente{ estilo de visualización (x:  sigma)  a  tau}Si M tiene tipo { estilo de visualización (x:  sigma)  a  tau}y N tiene tipo σ, entonces la aplicación { estilo de visualización M (N)}tiene tipo { estilo de visualización  tau [x: = N]}.
producto dependiente{ estilo de visualización (x:  sigma)  veces  tau}Si M tiene tipo { estilo de visualización (x:  sigma)  veces  tau}, entonces { estilo de visualización M = (N, O)}es un par tal que N tiene tipo σ y O tiene tipo { estilo de visualización  tau [x: = N]}.
Intersección dependiente{ estilo de visualización (x:  sigma)  cap  tau}Si M tiene tipo { estilo de visualización (x:  sigma)  cap  tau}, entonces M tiene tipo σ y M tiene tipo { estilo de visualización  tau [x: = M]}.
Intersección familiar{ estilo de visualización  bigcap _ {x:  sigma}  tau}Si M tiene tipo { estilo de visualización  bigcap _ {x:  sigma}  tau}, entonces M tiene tipo { estilo de visualización  tau [x: = N]}para cualquier término N de tipo σ.
unión familiar{ estilo de visualización  bigcup _ {x:  sigma}  tau}Si M tiene tipo { estilo de visualización  bigcup _ {x:  sigma}  tau}, entonces M tiene tipo { estilo de visualización  tau [x: = N]}para algún término N de tipo σ.

Tipos dependientes

Los tipos dependientes se basan en la idea de usar escalares o valores para describir con mayor precisión el tipo de algún otro valor. Por ejemplo, {displaystyle mathrm {matriz} (3,3)}podría ser el tipo de una 3 veces 3matriz. Luego podemos definir reglas de escritura como la siguiente regla para la multiplicación de matrices:{displaystyle mathrm {matriz} _ {mathrm {multiplicar} }:mathrm {matriz} (k,m)times mathrm {matriz} (m,n)to mathrm {matriz} (k,n)}

donde k, m, n son valores enteros positivos arbitrarios. Se ha creado una variante de ML llamada Dependent ML basada en este sistema de tipos, pero debido a que la verificación de tipos para los tipos dependientes convencionales es indecidible, no todos los programas que los usan se pueden verificar sin algún tipo de límite. El ML dependiente limita el tipo de igualdad que puede decidir a la aritmética de Presburger.

Otros lenguajes como Epigram hacen que el valor de todas las expresiones en el lenguaje sea decidible para que la verificación de tipos pueda ser decidible. Sin embargo, en general, la prueba de decidibilidad es indecidible, por lo que muchos programas requieren anotaciones escritas a mano que pueden no ser triviales. Como esto impide el proceso de desarrollo, muchas implementaciones de lenguaje ofrecen una salida fácil en forma de una opción para desactivar esta condición. Sin embargo, esto tiene el costo de hacer que el verificador de tipos se ejecute en un bucle infinito cuando se alimentan programas que no verifican el tipo, lo que hace que la compilación falle.

Tipos lineales

Los tipos lineales, basados ​​en la teoría de la lógica lineal, y estrechamente relacionados con los tipos de unicidad, son tipos asignados a valores que tienen la propiedad de tener una y sólo una referencia a ellos en todo momento. Estos son valiosos para describir grandes valores inmutables como archivos, cadenas, etc., porque cualquier operación que destruya simultáneamente un objeto lineal y cree un objeto similar (como 'str= str + "a"') se puede optimizar "debajo del capó" en una mutación en el lugar. Normalmente esto no es posible, ya que tales mutaciones podrían causar efectos secundarios en partes del programa que contienen otras referencias al objeto, violando la transparencia referencial. También se utilizan en el prototipo del sistema operativo Singularity para la comunicación entre procesos, asegurando estáticamente que los procesos no puedan compartir objetos en la memoria compartida para evitar condiciones de carrera. El lenguaje limpio (un lenguaje similar a Haskell) utiliza este tipo de sistema para ganar mucha velocidad (en comparación con la realización de una copia profunda) sin dejar de ser seguro.

Tipos de intersección

Los tipos de intersección son tipos que describen valores que pertenecen a otros dos tipos dados con conjuntos de valores superpuestos. Por ejemplo, en la mayoría de las implementaciones de C, el carácter con signo tiene un rango de -128 a 127 y el carácter sin signo tiene un rango de 0 a 255, por lo que el tipo de intersección de estos dos tipos tendría un rango de 0 a 127. Tal tipo de intersección podría pasarse con seguridad en funciones que esperan caracteres firmados o no firmados, porque es compatible con ambos tipos .

Los tipos de intersección son útiles para describir tipos de funciones sobrecargadas: por ejemplo, si " → " es el tipo de funciones que toman un argumento entero y devuelven un número entero, y " → " es el tipo de funciones que toman un argumento flotante y lo devuelven, entonces la intersección de estos dos tipos se puede usar para describir funciones que hacen una u otra, según el tipo de entrada que se les dé. Tal función podría pasarse a otra función esperando una función " → " de forma segura; simplemente no usaría la funcionalidad " → ". intintfloatfloatintintfloatfloat

En una jerarquía de subclases, la intersección de un tipo y un tipo antepasado (como su padre) es el tipo más derivado. La intersección de tipos hermanos está vacía.

El lenguaje de Forsythe incluye una implementación general de tipos de intersección. Una forma restringida son los tipos de refinamiento.

Tipos de unión

Los tipos de unión son tipos que describen valores que pertenecen a cualquiera de dos tipos. Por ejemplo, en C, el carácter firmado tiene un rango de -128 a 127, y el carácter sin firmar tiene un rango de 0 a 255, por lo que la unión de estos dos tipos tendría un rango "virtual" general de -128 a 255 que puede utilizarse parcialmente según a qué miembro de la unión se acceda. Cualquier función que maneje este tipo de unión tendría que manejar números enteros en este rango completo. Más generalmente, las únicas operaciones válidas en un tipo de unión son las operaciones que son válidas en ambos tipos que se unen. El concepto de "unión" de C es similar a los tipos de unión, pero no es seguro para tipos, ya que permite operaciones que son válidas en cualquier tipo, en lugar de en ambos.. Los tipos de unión son importantes en el análisis de programas, donde se utilizan para representar valores simbólicos cuya naturaleza exacta (por ejemplo, valor o tipo) no se conoce.

En una jerarquía de subclases, la unión de un tipo y un tipo ancestro (como su padre) es el tipo ancestro. La unión de tipos hermanos es un subtipo de su ancestro común (es decir, todas las operaciones permitidas en su ancestro común están permitidas en el tipo de unión, pero también pueden tener otras operaciones válidas en común).

Tipos existenciales

Los tipos existenciales se utilizan con frecuencia en relación con los tipos de registro para representar módulos y tipos de datos abstractos, debido a su capacidad para separar la implementación de la interfaz. Por ejemplo, el tipo "T = ∃X { a: X; f: (X → int); }" describe una interfaz de módulo que tiene un miembro de datos llamado a de tipo X y una función llamada f que toma un parámetro del mismo tipo X y devuelve un entero. Esto podría implementarse de diferentes maneras; por ejemplo:

Estos tipos son ambos subtipos del tipo T existencial más general y corresponden a tipos de implementación concretos, por lo que cualquier valor de uno de estos tipos es un valor de tipo T. Dado un valor "t" de tipo "T", sabemos que " tf(ta)" está bien tipificado, independientemente de cuál sea el tipo abstracto X. Esto brinda flexibilidad para elegir tipos adecuados para una implementación particular, mientras que los clientes que usan solo valores del tipo de interfaz, el tipo existencial, están aislados de estas opciones.

En general, es imposible para el verificador de tipos inferir a qué tipo existencial pertenece un módulo dado. En el ejemplo anterior intT { a: int; f: (int → int); } también podría tener el tipo ∃X { a: X; f: (int → int); }. La solución más simple es anotar cada módulo con su tipo previsto, por ejemplo:

Aunque los tipos y módulos de datos abstractos se habían implementado en los lenguajes de programación durante bastante tiempo, no fue hasta 1988 que John C. Mitchell y Gordon Plotkin establecieron la teoría formal bajo el lema: "Los tipos [de datos] abstractos tienen un tipo existencial". La teoría es un cálculo lambda tipado de segundo orden similar al Sistema F, pero con cuantificación existencial en lugar de universal.

Mecanografía gradual

La escritura gradual es un sistema de tipos en el que se puede asignar un tipo a las variables en tiempo de compilación (que es escritura estática) o en tiempo de ejecución (que es escritura dinámica), lo que permite a los desarrolladores de software elegir cualquier tipo de paradigma según corresponda, desde dentro. un solo idioma En particular, la tipificación gradual usa un tipo especial llamado dinámico para representar tipos estáticamente desconocidos, y la tipificación gradual reemplaza la noción de igualdad de tipos con una nueva relación llamada consistencia que relaciona el tipo dinámico con todos los demás tipos. La relación de consistencia es simétrica pero no transitiva.

Declaración e inferencia explícitas o implícitas

Muchos sistemas de tipo estático, como los de C y Java, requieren declaraciones de tipo: el programador debe asociar explícitamente cada variable con un tipo específico. Otros, como el de Haskell, realizan inferencia de tipos: el compilador saca conclusiones sobre los tipos de variables en función de cómo los programadores usan esas variables. Por ejemplo, dada una función que suma y junta, el compilador puede inferir que deben ser números, ya que la suma solo se define para números. Por lo tanto, cualquier llamada a otra parte del programa que especifique un tipo no numérico (como una cadena o una lista) como argumento indicaría un error. f(x, y)xyxyf

Las constantes numéricas y de cadena y las expresiones en el código pueden y, a menudo, implican tipo en un contexto particular. Por ejemplo, una expresión 3.14podría implicar un tipo de punto flotante, mientras que podría implicar una lista de enteros, normalmente una matriz. [1, 2, 3]

La inferencia de tipos es posible en general, si es computable en el sistema de tipos en cuestión. Además, incluso si la inferencia no es computable en general para un tipo de sistema dado, la inferencia es a menudo posible para un gran subconjunto de programas del mundo real. El sistema de tipos de Haskell, una versión de Hindley-Milner, es una restricción del Sistema Fω a los llamados tipos polimórficos de rango 1, en los que la inferencia de tipos es computable. La mayoría de los compiladores de Haskell permiten el polimorfismo de rango arbitrario como una extensión, pero esto hace que la inferencia de tipos no sea computable. (Sin embargo, la verificación de tipo es decidible y los programas de rango 1 aún tienen inferencia de tipo; los programas polimórficos de rango superior se rechazan a menos que se les proporcionen anotaciones de tipo explícitas).

Problemas de decisión

Un sistema de tipos que asigna tipos a términos en entornos de tipos usando reglas de tipos está naturalmente asociado con los problemas de decisión de verificación de tipos, tipificación y habitabilidad de tipos.

Sistema de tipo unificado

Algunos lenguajes como C# o Scala tienen un sistema de tipos unificado. Esto significa que todos los tipos de C#, incluidos los tipos primitivos, heredan de un único objeto raíz. Cada tipo en C# hereda de la clase Object. Algunos lenguajes, como Java y Raku, tienen un tipo raíz pero también tienen tipos primitivos que no son objetos. Java proporciona tipos de objetos envoltorios que existen junto con los tipos primitivos para que los desarrolladores puedan usar los tipos de objetos envoltorios o los tipos primitivos que no son objetos más simples. Raku convierte automáticamente tipos primitivos en objetos cuando se accede a sus métodos.

Compatibilidad: equivalencia y subtipificación

Un verificador de tipos para un lenguaje de tipos estáticos debe verificar que el tipo de cualquier expresión sea consistente con el tipo esperado por el contexto en el que aparece esa expresión. Por ejemplo, en una sentencia de asignación de la forma, el tipo inferido de la expresión debe ser coherente con el tipo declarado o inferido de la variable. Esta noción de consistencia, llamada compatibilidad, es específica de cada lenguaje de programación. x:= eex

Si el tipo de ey el tipo de xson iguales y se permite la asignación para ese tipo, esta es una expresión válida. Así, en los sistemas de tipos más simples, la cuestión de si dos tipos son compatibles se reduce a si son iguales (o equivalentes). Sin embargo, diferentes idiomas tienen diferentes criterios para cuando se entiende que dos expresiones de tipo denotan el mismo tipo. Estas diferentes teorías ecuacionales de tipos varían ampliamente, siendo dos casos extremos los sistemas de tipos estructurales, en los que dos tipos cualesquiera que describen valores con la misma estructura son equivalentes, y los sistemas de tipos nominativos, en los que no hay dos expresiones de tipo sintácticamente distintas que denoten el mismo tipo (es decir, los tipos deben tener el mismo "nombre" para ser iguales).

En lenguajes con subtipado, la relación de compatibilidad es más compleja. En particular, si Bes un subtipo de, entonces se puede usar Aun valor de tipo en un contexto donde se espera uno de tipo (covariante), incluso si lo contrario no es cierto. Al igual que la equivalencia, la relación de subtipo se define de manera diferente para cada lenguaje de programación, con muchas variaciones posibles. La presencia de polimorfismo paramétrico o ad hoc en un lenguaje también puede tener implicaciones para la compatibilidad de tipos. BA