Sistema de tipos

Concepto de informática

En programación de computadoras , un sistema de tipos es un sistema lógico que comprende un conjunto de reglas que asigna una propiedad llamada tipo (por ejemplo, entero , punto flotante , cadena ) a cada término (una palabra, frase u otro conjunto de símbolos). Generalmente los términos son varias construcciones del lenguaje de un programa de computadora , como variables , expresiones , funciones o módulos . ^[1] Un sistema de tipos dicta las operaciones que se pueden realizar en un término. Para las variables, el sistema de tipos determina los valores permitidos de ese término. Los sistemas de tipos formalizan y aplican las categorías implícitas que el programador utiliza para tipos de datos algebraicos , estructuras de datos u otros componentes (por ejemplo, "cadena", "matriz de flotante", "función que devuelve booleano").

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 puede ampliarse mediante herramientas opcionales que realizan comprobaciones adicionales utilizando la sintaxis y gramática de tipos originales del lenguaje. El objetivo principal de un sistema de tipos en un lenguaje de programación es reducir las posibilidades de que se produzcan errores en los programas informáticos debido a errores de tipo . ^[2] El sistema de tipos dado en cuestión determina lo que constituye un error de tipo, pero en general, el objetivo es evitar que operaciones que esperan un cierto tipo de valor se utilicen con valores para los cuales esa operación no tiene sentido (errores de validez). Los sistemas de tipos permiten definir interfaces entre diferentes partes de un programa de computadora y luego verificar 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 envíos múltiples y proporcionar una forma de documentación .

Resumen de uso

Un ejemplo de sistema de tipos 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 indica 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 que invoca indica 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 un almacenamiento temporal y 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 los utiliza. Si las instrucciones dentro de la función se escriben con el supuesto 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 verifica los tipos de argumentos pasados ​​a una función cuando se llama con los tipos de parámetros declarados en la definición de la función. Si los tipos no coinciden, el compilador genera un error o una advertencia en tiempo de compilación.

Un compilador también puede utilizar el tipo estático de un valor para optimizar el almacenamiento que necesita y la elección de algoritmos para las operaciones con 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 coma flotante sobre esos valores (suma de coma flotante, multiplicación, etc.).

La profundidad de las restricciones de tipo y la forma de su evaluación afectan la tipificación del idioma. 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 los enteros y las cadenas, dependen de cuestiones prácticas de arquitectura informática, implementación del compilador y 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 de ejecución, anotado manualmente o inferido automáticamente. Como lo expresó de manera concisa Mark Manasse: ^[3]

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 es posible que a los programas significativos no se les atribuyan significados. La búsqueda de sistemas tipográficos más ricos resulta de esta tensión.

La asignación de un tipo de datos, denominada escritura , 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 es incapaz de 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 ninguna distinción intrínseca entre ninguno de los valores posibles que una secuencia de bits podría significar . ^{[nota 1]} 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 llamadas tipo de datos (un tipo de valor), clase (un tipo de objeto) y clase (un tipo de 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 al programador anotar código o considerar operaciones y funcionamiento relacionados con la computadora. Es un desafío encontrar un sistema de tipos suficientemente expresivo que satisfaga todas las prácticas de programación de una manera segura .

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 los simples pares de tipo-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. Así, el sistema simbólico puede ser un sistema de tipo y efecto , lo que le confiere más control de seguridad que el control de tipo solo.

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 que ofrecen los sistemas de tipos especificados por el programador incluyen:

• Abstracción (o modularidad ): los tipos permiten a los programadores pensar en un nivel superior al del bit o el byte, sin preocuparse por la implementación de bajo nivel. Por ejemplo, los programadores pueden empezar a pensar en una cadena como un conjunto de valores de caracteres en lugar de una simple matriz de bytes. Más aún, los tipos permiten a los programadores imaginar y expresar interfaces entre dos subsistemas de cualquier tamaño. Esto permite más niveles de localización para que las definiciones requeridas para la interoperabilidad de los subsistemas sigan siendo consistentes cuando esos dos subsistemas se comunican.
• Documentación : en sistemas de tipos más expresivos, los tipos pueden servir como una forma de documentación que aclara la intención del programador. Por ejemplo, si un programador declara que una función devuelve un tipo de marca de tiempo, esto documenta la función cuando el tipo de marca de tiempo se puede declarar explícitamente más profundamente en el código como un tipo entero.

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

• Optimización : la verificación de tipos estática puede proporcionar información útil en tiempo de compilación. Por ejemplo, si un tipo requiere que un valor se alinee en la memoria en un múltiplo de cuatro bytes, el compilador puede utilizar instrucciones de máquina más eficientes.
• Seguridad : un sistema de tipos permite al compilador detectar código no válido o sin sentido. Por ejemplo, podemos identificar una expresión 3 / "Hello, World"como no válida, cuando las reglas no especifican cómo dividir un número entero por una cadena . La escritura fuerte ofrece más seguridad, pero no puede garantizar una seguridad de escritura completa .

Errores de tipo

Un error de tipo ocurre cuando una operación recibe un tipo de datos diferente al esperado. ^[4] Por ejemplo, se produciría un error de tipo si una línea de código divide dos números enteros y se le pasa una cadena de letras en lugar de un número entero. ^[4] Es una condición no deseada ^{[nota 2]} que podría manifestarse en múltiples etapas del desarrollo de un programa. Por 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, el compilador puede disponer de lint 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 sea un problema indecidible (como en el problema de detención ). En un sistema de tipos con verificación de tipos automatizada, es posible que un programa se ejecute incorrectamente pero no produzca errores de compilación. La división por cero es una operación insegura e incorrecta, pero un verificador de tipos que sólo se ejecuta en tiempo de compilación no busca la división por cero en la mayoría de los lenguajes; esa división surgiría como un error de tiempo de ejecución . Para demostrar la ausencia de estos defectos, se utilizan comúnmente otros tipos de métodos formales , conocidos colectivamente como análisis de programas . Alternativamente, un sistema de tipos suficientemente expresivo, como en los lenguajes escritos de forma dependiente, puede evitar 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 dicho verificador de tipos no detectaría.

Comprobación de tipo

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

Comprobación de tipo estático

La verificación de tipos estática es el proceso de verificar la seguridad de tipos de un programa basándose en el análisis del texto de un programa ( código fuente ). Si un programa pasa un verificador de tipo estático, entonces 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ática puede considerarse una forma limitada de verificación de programas (consulte seguridad de tipos ) y, en un lenguaje con seguridad de tipos, también puede considerarse una optimización. Si un compilador puede demostrar que un programa está bien tipado, 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 ejecución). ^[7] Por ejemplo, considere un programa que contiene 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 como trueen tiempo de ejecución, la mayoría de los verificadores de tipos rechazarán el programa por estar mal escrito, porque es difícil (si no imposible) para un analizador estático determinar que elseno se tomará la rama. ^[8] En consecuencia, un verificador de tipo estático detectará rápidamente errores de tipo en rutas de código poco utilizadas. Sin una verificación de tipo estática, incluso las pruebas de cobertura de código con una cobertura del 100% pueden no poder encontrar dichos errores de tipo. Es posible que las pruebas no detecten dichos errores de tipo, porque 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.

Varias características útiles y comunes del lenguaje de programación no se pueden verificar estáticamente, 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 comprobaciones dinámicas verifican el resto.

Muchos lenguajes con verificación de tipo estática proporcionan una forma de evitar el verificador de tipo. Algunos lenguajes permiten a los programadores elegir entre seguridad de tipo estático y dinámico. Por ejemplo, históricamente C# declara variables estáticamente, ^{[9] : 77, Sección 3.2} , pero C# 4.0 introduce la dynamicpalabra clave, que se utiliza para declarar variables que se comprobarán dinámicamente en tiempo de ejecución. ^{[9] : 117, Sección 4.1} 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 cualesquiera 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 de verificación de tipos dinámicamente 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 despacho dinámico , enlace tardío , downcasting , programación reflexiva (reflexión) y características similares.

La mayoría de los lenguajes con seguridad de tipos incluyen alguna forma de verificación de tipos dinámica, incluso si también tienen un verificador de tipos estático. ^[10] La razón de esto es que muchas características o propiedades útiles son difíciles o imposibles de verificar estáticamente. Por ejemplo, supongamos que un programa define dos tipos, A y B, donde B es un subtipo de A. Si el programa intenta convertir un valor del tipo A al tipo B, lo que se conoce como downcasting , 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 sea segura. Este requisito es una de las críticas al abatimiento.

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

Los lenguajes de programación que incluyen verificación de tipos dinámicos pero no verificación de tipos estática 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 tipados dinámicamente .

Combinando verificación de tipos estática y dinámica

Algunos idiomas permiten escritura tanto estática como dinámica. Por ejemplo, Java y algunos otros lenguajes aparentemente de tipo estático 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 del tipo en tiempo de ejecución. Otro ejemplo es C++ RTTI . De manera más general, la mayoría de los lenguajes de programación incluyen mecanismos para distribuir diferentes "tipos" de datos, como uniones disjuntas , polimorfismo en tiempo de ejecución y tipos variantes . Incluso cuando no interactúan con anotaciones de tipo o verificación de tipos, dichos mecanismos son materialmente similares a las implementaciones de escritura dinámica. Consulte lenguaje de programación para obtener más información sobre las interacciones entre escritura estática y dinámica.

Generalmente se accede a los objetos en lenguajes orientados a objetos 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 a un supertipo del mismo. Esto se ajusta al 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 argumentos covariantes o contravariantes, respectivamente.

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

Por el contrario, a partir de la versión 4.0, el lenguaje C# proporciona una manera de indicar que una variable no debe ser verificada estáticamente. Una variable cuyo tipo sea dynamicno estará sujeta a 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 utilizar la variable. ^{[12] [9] : 113-119}

En Rust , el tipo proporciona tipificación dinámica de tipos. ^[13]dyn std::any::Any'static

Comprobación de tipos estática y dinámica 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 confiable en tiempo de 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 mayores desacuerdos sobre la proporción de esos errores codificados que se detectarían si se representaran adecuadamente los tipos diseñados en el código. ^{[14] [15]} Defensores de la escritura estática ^{[ ¿quién? ]} creen que los programas son más confiables cuando han sido bien verificados, mientras que los defensores de la escritura dinámica ^{[ ¿quién? ]} señalan código distribuido que ha demostrado ser confiable y bases de datos de pequeños errores. ^{[ cita necesaria ]} El valor de la escritura estática aumenta a medida que aumenta la solidez del sistema de tipos. Defensores de la mecanografía dependiente , ^{[ ¿quién? ]} 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. ^[dieciséis]

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 código de máquina optimizado. Algunos lenguajes de tipo 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 dinámicamente código nuevo, porque los cambios en el código fuente en lenguajes escritos dinámicamente pueden resultar en menos comprobaciones que realizar y menos código que revisar. ^{[ se necesita aclaración ]} Esto también puede reducir el ciclo de edición-compilación-prueba-depuración.

Los lenguajes de tipo estático que carecen de inferencia de tipos (como C y Java anteriores a la versión 10 ) requieren que los programadores declaren los tipos que debe utilizar 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 pierda la sincronía y que los programadores lo ignoren. Sin embargo, un lenguaje se puede escribir estáticamente sin requerir declaraciones de tipo (los ejemplos incluyen Haskell , Scala , OCaml , F# , Swift 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 escritura dinámica permite construcciones que alguna verificación de tipo estático (simple) rechazaría como ilegal. Por ejemplo, son posibles las funciones de evaluación , que ejecutan datos arbitrarios como código. Una función de evaluación 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 permite una reutilización de código más fácil ). Muchos lenguajes ^{[ especifique ]} con escritura estática también cuentan con escritura pato u otros mecanismos como programación genérica que también permiten una reutilización de código más sencilla.

La escritura dinámica normalmente hace que la metaprogramación sea más fácil de usar. Por ejemplo, las plantillas de C++ suelen ser más complicadas de escribir que el código Ruby o Python equivalente, ya que C++ tiene reglas más estrictas con respecto a las definiciones de tipos (tanto para funciones como para variables). Esto obliga a un desarrollador a escribir más código repetitivo para una plantilla del 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 tipo estático. En algunos lenguajes, estas características también se pueden utilizar, por ejemplo, para generar nuevos tipos y comportamientos sobre la marcha, basándose en datos en tiempo de ejecución. Estas construcciones avanzadas suelen ser proporcionadas por lenguajes de programación dinámicos ; muchos de ellos se escriben dinámicamente, aunque la escritura dinámica no tiene por qué estar relacionada con los lenguajes de programación dinámicos .

Sistemas de tipos fuertes y débiles.

Los idiomas a menudo se denominan coloquialmente tipificados fuertemente o débilmente tipificados . 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".

Seguridad de tipos y seguridad de 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 escritas. Los informáticos utilizan el término lenguaje de tipo seguro 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 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 causarán errores en tiempo de compilación y quizás en tiempo de ejecución.

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

varx:= 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 aún así fallar en una operación no válida. Esto es para lenguajes donde el sistema de tipos no es lo suficientemente avanzado como 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 para tipos, terminar el programa suele ser la única opción.

Consideremos ahora un ejemplo similar en C:

int x = 5 ; char y [] = "37" ; carbón * z = x + y ; printf ( "%c \n " , * z );            

En este ejemplo, zapuntará a una dirección de memoria cinco caracteres más allá de y, equivalente a tres caracteres después del carácter cero final de la cadena señalada por y. Esta es la memoria a la que no se espera que acceda el programa. En términos de C, esto es simplemente un comportamiento indefinido y el programa puede hacer cualquier cosa; con un compilador simple podría imprimir cualquier byte almacenado después de la cadena "37". Como muestra este ejemplo, C no es seguro para la memoria. Como se suponía que los datos arbitrarios eran un carácter, tampoco es un lenguaje con seguridad de tipos.

En general, la seguridad de tipos y la seguridad de la memoria van de la mano. Por ejemplo, un lenguaje que admite 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 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 aplicar diferentes niveles de verificación a diferentes regiones de código. Ejemplos incluyen:

• La use strictdirectiva en JavaScript ^{[18] [19] [20]} y Perl aplica una verificación más estricta.
• En PHP ^[21],declare(strict_types=1) por archivo, solo se aceptará una variable del tipo exacto de la declaración de tipo, o se arrojará una.TypeError
• En VB.NETOption Strict On permite que el compilador requiera una conversión entre objetos.

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

Sistemas de tipo opcional

Se ha propuesto, principalmente por Gilad Bracha , que la elección del sistema de tipos se haga independiente de la elección del idioma; que un sistema de tipos debe ser un módulo que pueda conectarse 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. ^[22] El requisito de que el sistema de tipos no afecte la semántica del lenguaje es difícil de cumplir.

La escritura opcional está relacionada con la escritura gradual , pero es distinta de ella . Si bien ambas disciplinas de mecanografía se pueden utilizar para realizar análisis estáticos de código ( tipificación estática ), los sistemas de tipos opcionales no imponen la seguridad de tipos en tiempo de ejecución ( tipificación dinámica ). ^{[22] [23]}

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 a 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 sólo 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 tipo especializado.

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

La siguiente tabla ofrece una descripción general de los conceptos de teoría de tipos que se utilizan en sistemas de tipos especializados. Los nombres M, N, O abarcan términos y los nombres abarcan tipos. Se utilizará la siguiente notación: ${\displaystyle \sigma ,\tau }$

• ${\displaystyle M:\sigma }$significa que tiene tipo ; ${\displaystyle M}$ ${\displaystyle \sigma }$
• ${\displaystyle M(N)}$es esa aplicación de on ; ${\displaystyle M}$ ${\displaystyle N}$
• ${\displaystyle \tau [\alpha :=\sigma ]}$(resp. ) describe el tipo que resulta de reemplazar todas las apariciones de la variable de tipo α (resp. término variable x ) por el tipo σ (resp. término N ). ${\displaystyle \tau [x:=N]}$ ${\displaystyle \tau }$

1. También conocido como tipo de producto dependiente , desde entonces . ${\textstyle (x:\sigma )\to \tau =\prod _{x:\sigma }\tau }$
2. También conocido como tipo de suma dependiente , ya que . ${\textstyle (x:\sigma )\times \tau =\sum _{x:\sigma }\tau }$

Tipos dependientes

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

${\displaystyle \mathrm {matrix} _{\mathrm {multiply} }:\mathrm {matrix} (k,m)\times \mathrm {matrix} (m,n)\to \mathrm {matrix} (k,n)}$

donde k , m , n son valores enteros positivos arbitrarios. Se ha creado una variante de ML llamada ML dependiente basada en este sistema de tipos, pero debido a que la verificación de tipos para tipos dependientes convencionales es indecidible , no todos los programas que los utilizan se pueden verificar sin algún tipo de límites. 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 lenguajes brindan 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 los tipos, lo que provoca 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 "bajo el capó" en una mutación in situ. . 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 de 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 realizar una copia profunda) sin dejar de ser seguro.

Tipos de intersecciones

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 firmar 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. Un tipo de intersección de este tipo podría pasarse de forma segura en funciones que esperan caracteres con o sin signo, porque es compatible con ambos tipos.

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

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

El lenguaje 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 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 la unión de estos dos tipos tendría un rango "virtual" general de -128 a 255 que puede utilizarse parcialmente dependiendo del miembro del sindicato al que se acceda. Cualquier función que maneje este tipo de unión tendría que manejar números enteros en este rango completo. De manera más general, las únicas operaciones válidas en un tipo de unión son las operaciones que son válidas en ambos tipos que están unidos. El concepto de "unión" de C es similar a los tipos de unión, pero no es seguro para los tipos, ya que permite operaciones que son válidas en cualquiera de los tipos, 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) se desconoce.

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 conexión con tipos de registros 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 número entero. Esto podría implementarse de diferentes maneras; Por ejemplo:

• intT = { a: int; f: (int → entero); }
• flotadorT = { a: flotador; f: (flotante → int); }

Ambos tipos son subtipos del tipo existencial más general T 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 determinado. En el ejemplo anterior intT { a: int; f: (int → entero); } también podría tener el tipo ∃X { a: X; f: (int → entero); }. La solución más sencilla es anotar cada módulo con su tipo previsto, por ejemplo:

• intT = { a: int; f: (int → entero); } como ∃X { a: X; f: (X → int); }

Aunque los módulos y tipos 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". ^[25] La teoría es un cálculo lambda tipificado de segundo orden similar al Sistema F , pero con cuantificación existencial en lugar de universal.

Escritura gradual

En un sistema de tipos con escritura gradual , a las variables se les puede asignar un tipo en tiempo de compilación (que es escritura estática) o en tiempo de ejecución (que es escritura dinámica). ^[26] Esto permite a los desarrolladores de software elegir cualquier tipo de paradigma según corresponda, desde un solo idioma. ^[26] La escritura gradual utiliza un tipo especial llamado dinámico para representar tipos estáticamente desconocidos; 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. ^[27]

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

Muchos sistemas de tipos estáticos, como los de C y Java, requieren declaraciones de tipos : el programador debe asociar explícitamente cada variable a un tipo específico. Otros, como el de Haskell, realizan inferencia de tipos : el compilador saca conclusiones sobre los tipos de variables basándose en cómo los programadores usan esas variables. Por ejemplo, dada una función que suma y , el compilador puede inferir que y deben ser números, ya que la suma solo está definida 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 y expresiones numéricas y de cadena en el código pueden y a menudo implican escribir 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 números enteros, normalmente una matriz .[1, 2, 3]

En general, la inferencia de tipos es posible si es computable en el sistema de tipos en cuestión. Además, incluso si la inferencia no es computable en general para un sistema de tipo determinado, la inferencia a menudo es 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 extensión, pero esto hace que la inferencia de tipos no sea computable. (Sin embargo, la verificación de tipos es decidible y los programas de rango 1 todavía tienen inferencia de tipos; 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 tipográficos utilizando reglas de tipificación se asocia naturalmente con los problemas de decisión de verificación de tipos , tipificación y ocupación de tipos . ^[28]

• Dado un entorno de tipos , un término y un tipo , decida si al término se le puede asignar el tipo en el entorno de tipos. ${\displaystyle \Gamma }$ ${\displaystyle e}$ ${\displaystyle \tau }$ ${\displaystyle e}$ ${\displaystyle \tau }$
• Dado un término , decida si existe un entorno de tipos y un tipo tal que al término se le pueda asignar el tipo en el entorno de tipos . ${\displaystyle e}$ ${\displaystyle \Gamma }$ ${\displaystyle \tau }$ ${\displaystyle e}$ ${\displaystyle \tau }$ ${\displaystyle \Gamma }$
• Dado un entorno de tipos y un tipo , decida si existe un término al que se le pueda asignar el tipo en el entorno de tipos. ${\displaystyle \Gamma }$ ${\displaystyle \tau }$ ${\displaystyle e}$ ${\displaystyle \tau }$

Sistema de tipo unificado

Algunos lenguajes como C# o Scala tienen un sistema de tipos unificado. ^[29] 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 Objeto. Algunos lenguajes, como Java y Raku , tienen un tipo raíz pero también tipos primitivos que no son objetos. ^[30] Java proporciona tipos de objetos envolventes que existen junto con los tipos primitivos para que los desarrolladores puedan utilizar los tipos de objetos envolventes 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. ^[31]

Compatibilidad: equivalencia y subtipificación

Un verificador de tipos para un lenguaje de tipado estático 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 declaración 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 coherencia, 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, entonces 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 la de si son iguales (o equivalentes ). Sin embargo, diferentes idiomas tienen diferentes criterios para entender cuándo 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 tipos sintácticamente distintas que denoten el mismo tipo ( es decir , los tipos deben tener el mismo "nombre" para ser iguales).

En lenguajes con subtipos , la relación de compatibilidad es más compleja: si Bes un subtipo de A, entonces un valor de tipo Bse puede usar en un contexto donde Ase 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 forma diferente para cada lenguaje de programación, con muchas variaciones posibles. La presencia de polimorfismo paramétrico o ad hoc en un idioma también puede tener implicaciones para la compatibilidad de tipos.

Ver también

• portal de programación informática

• Comparación de sistemas de tipos.
• Covarianza y contravarianza (informática)
• Polimorfismo en programación orientada a objetos
• Escriba la firma
• Teoría de tipos

Notas

1. La línea de computadoras Burroughs ALGOL determinó el contenido de una ubicación de memoria mediante sus bits de bandera. Los bits de bandera especifican el contenido de una ubicación de memoria. Las instrucciones, el tipo de datos y las funciones se especifican mediante un código de 3 bits además de su contenido de 48 bits. Sólo el MCP (Programa de control maestro) podía escribir en los bits del código de bandera.
2. Por ejemplo, puede surgir una abstracción con fugas durante el desarrollo, lo que puede mostrar que se necesita más desarrollo de tipos. —"La evaluación de un programa bien tipificado siempre termina".—B. Nordström, K. Petersson y JM Smith ^[5] Un cambio sistemático en las variables para evitar la captura de una variable libre puede introducir errores en un lenguaje de programación funcional donde las funciones son ciudadanos de primera clase. ^[6] —Del artículo sobre cálculo lambda .

Referencias

1. Perforar 2002, pag. 1: "Un sistema de tipos es un método sintáctico manejable para demostrar la ausencia de ciertos comportamientos del programa clasificando frases según los tipos de valores que calculan".
2. Cardelli 2004, pag. 1: "El propósito fundamental de un sistema de tipos es evitar la aparición de errores de ejecución durante la ejecución de un programa".
3. Perforar 2002, pag. 208.
4. Sethi, R. (1996). Lenguajes de programación: conceptos y construcciones (2ª ed.). Addison-Wesley. pag. 142.ISBN​ 978-0-201-59065-4. OCLC  604732680.
5. Nordstrom, B.; Petersson, K.; Smith, JM (2001). "Teoría de tipos de Martin-Löf". Estructuras algebraicas y lógicas . Manual de lógica en informática. vol. 5. Prensa de la Universidad de Oxford. pag. 2.ISBN​ 978-0-19-154627-3.
6. Turner, DA (12 de junio de 2012). "Un poco de historia de los lenguajes de programación funcionales" (PDF) . Conferencia invitada en TFP12, en la Universidad de St Andrews . Consulte la sección sobre Algol 60.
7. "... cualquier sistema de tipos sólido y decidible debe ser incompleto" —D. Rémy (2017). pag. 29, Rémy, Didier. «Sistemas de tipos para lenguajes de programación» (PDF) . Archivado desde el original (PDF) el 14 de noviembre de 2017 . Consultado el 26 de mayo de 2013 .
8. Perforar 2002.
9. Skeet, Jon (2019). C# en profundidad (4 ed.). Manning. ISBN 978-1617294532.
10. Miglani, Gaurav (2018). "Envío de métodos dinámicos o polimorfismo en tiempo de ejecución en Java". Archivado desde el original el 7 de diciembre de 2020 . Consultado el 28 de marzo de 2021 .
11. Wright, Andrew K. (1995). Escritura suave práctica (Doctor). Universidad de Rice. hdl : 1911/16900.
12. "dinámico (referencia de C#)". Biblioteca MSDN . Microsoft . Consultado el 14 de enero de 2014 .
13. "std::cualquiera - Óxido". doc.rust-lang.org . Consultado el 7 de julio de 2021 .
14. Meijer, Erik; Drayton, Peter. "Escritura estática cuando sea posible, escritura dinámica cuando sea necesario: el fin de la guerra fría entre lenguajes de programación" (PDF) . Corporación Microsoft .
15. Lanzador, Amanda; Snively, Paul (2012). "Tipos frente a pruebas". InformaciónQ.
16. Xi, Hongwei (1998). Tipos dependientes en programación práctica (Doctor). Departamento de Ciencias Matemáticas, Universidad Carnegie Mellon. CiteSeerX 10.1.1.41.548 . 
    Xi, Hongwei; Pfenning, Frank (1999). "Tipos dependientes en programación práctica". Actas del 26º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación . ACM. págs. 214-227. CiteSeerX  10.1.1.69.2042 . doi :10.1145/292540.292560. ISBN 1581130953. S2CID  245490.
17. Visual Basic es un ejemplo de un lenguaje que es seguro tanto para tipos como para memoria.
18. "4.2.2 La variante estricta de ECMAScript". Especificación del lenguaje ECMAScript® 2020 (11.a ed.). ECMA. Junio ​​de 2020. ECMA-262.
19. "Modo estricto: JavaScript". MDN . Desarrollador.mozilla.org. 2013-07-03 . Consultado el 17 de julio de 2013 .
20. "Modo estricto (JavaScript)". MSDN . Microsoft . Consultado el 17 de julio de 2013 .
21. "Mecanografía estricta". Manual PHP: Referencia del lenguaje: Funciones .
22. Bracha, G. "Tipos conectables" (PDF) .
23. "Claro. Se llama" escritura gradual ", y yo lo calificaría como moderno ..." ¿Existe algún lenguaje que permita la escritura tanto estática como dinámica? . desbordamiento de pila. 2012.
24. Kopylov, Alexei (2003). "Intersección dependiente: una nueva forma de definir registros en teoría de tipos". 18º Simposio IEEE sobre lógica en informática . LICS 2003. Sociedad de Computación IEEE. págs. 86–95. CiteSeerX 10.1.1.89.4223 . doi :10.1109/LICS.2003.1210048. 
25. Mitchell, John C.; Plotkin, Gordon D. (julio de 1988). "Los tipos abstractos tienen un tipo existencial" (PDF) . Transmisión ACM. Programa. Lang. Sistema . 10 (3): 470–502. doi :10.1145/44501.45065. S2CID  1222153.
26. Siek, Jeremy (24 de marzo de 2014). "¿Qué es la mecanografía gradual?".
27. Siek, Jeremy; Taha, Walid (septiembre de 2006). Escritura gradual para lenguajes funcionales (PDF) . Esquema y Programación Funcional 2006 . Universidad de Chicago . págs. 81–92.
28. Barendregt, Henk; Dekkers, Wil; Statman, Richard (20 de junio de 2013). Cálculo Lambda con tipos. Prensa de la Universidad de Cambridge. pag. 66.ISBN​ 978-0-521-76614-2.
29. "8.2.4 Unificación del sistema de tipos". Especificación del lenguaje C# (5ª ed.). ECMA. Diciembre de 2017. ECMA-334.
30. "Tipos nativos". Documentación de Perl 6 .
31. "Números, § Boxeo automático". Documentación de Perl 6 .

Otras lecturas

• Cardelli, Luca ; Wegner, Peter (diciembre de 1985). "Sobre la comprensión de los tipos, la abstracción de datos y el polimorfismo" (PDF) . Encuestas de Computación ACM . 17 (4): 471–523. CiteSeerX  10.1.1.117.695 . doi :10.1145/6041.6042. S2CID  2921816.
• Pierce, Benjamín C. (2002). Tipos y Lenguajes de Programación . Prensa del MIT. ISBN 978-0-262-16209-8.
• Cardelli, Luca (2004). "Sistemas de tipos" (PDF) . En Allen B. Tucker (ed.). Manual CRC de ingeniería y ciencias de la computación (2ª ed.). Prensa CRC. ISBN 978-1584883609.
• Tratt, Laurence (julio de 2009). "5. Idiomas escritos dinámicamente". Avances en Computadoras . vol. 77. Elsevier. págs. 149–184. doi :10.1016/S0065-2458(09)01205-4. ISBN 978-0-12-374812-6.

enlaces externos

• Medios relacionados con los sistemas tipográficos en Wikimedia Commons
• Smith, Chris (2011). "Qué saber antes de debatir los sistemas tipográficos".