Sistema de tipos

Concepto de informática

En programación informática , un sistema de tipos es un sistema lógico que comprende un conjunto de reglas que asignan una propiedad llamada tipo (por ejemplo, entero , punto flotante , cadena ) a cada término (una palabra, frase u otro conjunto de símbolos). Por lo general, los términos son varias construcciones del lenguaje de un programa informático , 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 refuerzan las categorías implícitas que el programador utiliza para tipos de datos algebraicos , estructuras de datos u otros tipos de datos , como "cadena", "matriz de puntos flotantes" o "función que devuelve un valor booleano".

Los sistemas de tipos a menudo se especifican como parte de los lenguajes de programación y se incorporan a los intérpretes y compiladores , aunque el sistema de tipos de un lenguaje se puede ampliar mediante herramientas opcionales que realizan comprobaciones adicionales utilizando la sintaxis y la 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 errores en los programas informáticos debido a errores de tipo . ^[2] El sistema de tipos 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 cuales esa operación no tiene sentido (errores de validez).

Los sistemas de tipos permiten definir interfaces entre distintas partes de un programa informático y, a continuación, comprobar que las partes se han conectado de forma coherente. Esta comprobación puede realizarse de forma estática (en tiempo de compilación ), dinámica (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 de negocio, permitir ciertas optimizaciones del compilador , permitir el envío múltiple y proporcionar una forma de documentación .

Descripción general del uso

Un ejemplo de un 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 de un programa informático , los valores se almacenan temporalmente 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 pasa un valor de punto flotante , la función invocada calculará un resultado incorrecto.

El compilador de C compara los tipos de los argumentos que se pasan a una función cuando se la llama con 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 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 sobre el valor. En muchos compiladores de C, el tipo de datos float , por ejemplo, se representa en 32 bits , de acuerdo con la especificación IEEE para números de punto flotante de precisión simple . Por lo tanto, utilizarán operaciones de microprocesador específicas de punto flotante sobre esos valores (suma, multiplicación, etc. de punto flotante).

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 asociar además 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 números enteros y las cadenas, dependen de cuestiones prácticas de arquitectura informática , implementación de compiladores y diseño de lenguajes .

Fundamentos

Formalmente, la teoría de tipos estudia los sistemas de tipos. Un lenguaje de programación debe tener la oportunidad de verificar los 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ó concisamente Mark Manasse: ^[3]

El problema fundamental que aborda una teoría de tipos es asegurar que los programas tengan significado. El problema fundamental que plantea 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 es el resultado de esta tensión.

La asignación de un tipo de datos, denominada tipificación , otorga 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, por ejemplo, entre una dirección de memoria y un código de instrucción , o entre un carácter , un entero o un número de punto flotante , porque no hace ninguna distinción intrínseca entre ninguno de los posibles valores que una secuencia de bits podría significar . ^{[nota 1]} La asociación de 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. Una implementación de un sistema de tipos podría, en teoría, asociar identificaciones llamadas tipo de datos (un tipo de un valor), clase (un tipo de un objeto) y clase (un tipo de un tipo o metatipo). Estas son las abstracciones por las que puede pasar la tipificación, 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 precisas 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 el programador debe prestar más atención a la anotación del código o a la consideración de 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 para los tipos .

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 pares de valor-tipo simples, una "región" virtual de código se asocia 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 tipos y efectos , lo que le otorga más control de seguridad que el control de tipos solo.

Ya sea que el compilador lo automatice o lo especifique un programador, un sistema de tipos hace que el comportamiento del programa sea ilegal si no cumple 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 molestarse en realizar implementaciones de bajo nivel . Por ejemplo, los programadores pueden empezar a pensar en una cadena como un conjunto de valores de caracteres en lugar de como una mera matriz de bytes. Más arriba aún, los tipos permiten a los programadores pensar y expresar interfaces entre dos subsistemas de cualquier tamaño. Esto permite más niveles de localización para que las definiciones necesarias para la interoperabilidad de los subsistemas sigan siendo coherentes 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 clarifique 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 adelante en el código como un tipo entero.

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

• Optimización : la comprobació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 sin sentido o inválido. Por ejemplo, podemos identificar una expresión 3 / "Hello, World"como inválida cuando las reglas no especifican cómo dividir un entero por una cadena . La tipificación fuerte ofrece más seguridad, pero no puede garantizar una seguridad de tipos completa .

Errores de tipo

Un error de tipo ocurre cuando una operación recibe un tipo de datos diferente al esperado. ^[4] Por ejemplo, un error de tipo ocurriría 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 puede manifestarse en múltiples etapas del desarrollo de un programa. Por lo tanto, se necesita una función para la detección del error en el sistema de tipos. En algunos lenguajes, como Haskell , para los que la inferencia de tipos está automatizada, lint puede 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 sólo puede garantizar la corrección a costa de hacer que la comprobación de tipos en sí misma sea un problema indecidible (como en el problema de la detención ). En un sistema de tipos con comprobación de tipos automatizada, 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 tipos que sólo se ejecuta en tiempo de compilación no escanea en busca de divisiones por cero en la mayoría de los lenguajes; esa división aparecerí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 de tipado dependiente, puede prevenir este tipo de errores (por ejemplo, expresando el tipo de números distintos de cero ). Además, las pruebas de software son un método empírico para encontrar errores que un verificador de tipos de este tipo no detectaría.

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 (una verificación dinámica).

Si una especificación de lenguaje requiere reglas de tipado fuertemente estrictas, permitiendo más o menos solo aquellas conversiones de tipos automáticas que no pierden información, uno puede referirse al proceso como fuertemente tipado; si no, como débilmente tipado .

Los términos no suelen utilizarse en sentido estricto.

Comprobación de tipo estático

La comprobación de tipos estáticos 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 una comprobación de tipos estáticos, se garantiza que el programa satisface un conjunto de propiedades de seguridad de tipos para todas las entradas posibles.

La comprobación de tipos estática puede considerarse una forma limitada de verificación de programas (véase seguridad de tipos ) y, en un lenguaje de tipos seguros, también puede considerarse una optimización. Si un compilador puede demostrar que un programa está bien tipificado, 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 comprobación de tipos estática para lenguajes Turing-completos es inherentemente conservadora. Es decir, si un sistema de tipos es sólido (es decir, rechaza todos los programas incorrectos) y decidible (es decir, es posible escribir un algoritmo que determine si un programa está bien tipificado), entonces debe ser incompleto (es decir, hay programas correctos, que también se rechazan, 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 tipificado, 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 tipos estático detectará rápidamente errores de tipo en rutas de código raramente utilizadas. Sin la verificación de tipos estática, incluso las pruebas de cobertura de código con una cobertura del 100% pueden ser incapaces de encontrar tales errores de tipo. Las pruebas pueden fallar en detectar tales errores de tipo, porque se debe tener en cuenta la combinación de todos los lugares donde se crean valores y todos los lugares donde se usa un cierto valor.

Hay varias características útiles y comunes de los lenguajes de programación que no se pueden comprobar de forma estática, como por ejemplo la conversión descendente . Por lo tanto, muchos lenguajes tendrán comprobación de tipos tanto estática como dinámica; el comprobador de tipos estático verifica lo que puede y las comprobaciones dinámicas verifican el resto.

Muchos lenguajes con comprobación de tipos estática proporcionan una forma de evitar el verificador de tipos. Algunos lenguajes permiten a los programadores elegir entre seguridad de tipos estática y dinámica. 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 seguro para tipos; por ejemplo, en C , los programadores pueden convertir libremente un valor entre dos tipos cualesquiera que tengan el mismo tamaño, subvirtiendo efectivamente el concepto de tipo.

Comprobación de tipos dinámica e información de tipos en tiempo de ejecución

La comprobación de tipos dinámica es el proceso de verificar la seguridad de tipos de un programa en tiempo de ejecución. Las implementaciones de lenguajes con comprobación de tipos 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 el envío dinámico , el enlace tardío , la conversión descendente , la programación reflexiva (reflexión) y funciones 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 de tipo A a tipo B, lo que se conoce como conversión descendente , entonces la operación es legal solo 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 a la conversión descendente.

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

Los lenguajes de programación que incluyen verificación de tipos dinámica pero no verificación de tipos estática a menudo se denominan "lenguajes de programación tipados dinámicamente".

Combinación de comprobación de tipos estática y dinámica

Algunos lenguajes permiten tanto la tipificación estática como la dinámica. Por ejemplo, Java y otros lenguajes aparentemente de tipado estático admiten la conversión descendente de tipos a sus subtipos , la consulta de 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 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 comprobación de tipo, dichos mecanismos son materialmente similares a las implementaciones de tipado dinámico. Consulte lenguaje de programación para obtener más información sobre las interacciones entre tipado estático y dinámico.

Los objetos en lenguajes orientados a objetos suelen accederse mediante una referencia cuyo tipo de destino estático (o tipo manifiesto) es igual al tipo de tiempo de ejecución del objeto (su tipo latente) o a 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 lenguajes, los subtipos también pueden poseer tipos de retorno y tipos de argumento covariantes o contravariantes respectivamente.

Algunos lenguajes, como Clojure , Common Lisp o Cython , tienen una comprobación de tipos dinámica de forma predeterminada, pero permiten que los programas opten por la comprobación de tipos estática proporcionando 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 mediante la tipificación gradual. El entorno de programación DrRacket , un entorno pedagógico basado en Lisp y precursor del lenguaje Racket , también tiene tipificación suave. ^[11]

Por el contrario, a partir de la versión 4.0, el lenguaje C# proporciona una forma de indicar que una variable no debe ser objeto de una comprobación de tipo estática. Una variable cuyo tipo sea dynamicno estará sujeta a una comprobación de tipo estática. En cambio, el programa se basa en la información de tipo en tiempo de ejecución para determinar cómo se puede utilizar la variable. ^{[12] [9] : 113–119}

En Rust , el tipo proporciona tipado dinámico 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 tipado estático y dinámico requiere ciertas compensaciones .

El tipado estático puede encontrar errores de tipo de manera 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 de tipo, lo que resulta en más desacuerdos sobre la proporción de esos errores que están codificados que se detectarían al representar apropiadamente los tipos diseñados en el código. ^{[14] [15]} Los defensores del tipado estático ^{[ ¿quiénes? ]} creen que los programas son más confiables cuando han sido bien comprobados en cuanto a tipos, mientras que los defensores del tipado dinámico ^{[ ¿quiénes? ]} apuntan al código distribuido que ha demostrado ser confiable y a pequeñas bases de datos de errores. ^{[ cita requerida ]} El valor del tipado estático aumenta a medida que aumenta la fuerza del sistema de tipos. Los defensores del tipado dependiente , ^{[ ¿quiénes? ]} 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. ^[16]

El tipado estático suele dar como resultado un código compilado que se ejecuta más rápido. Cuando el compilador conoce los tipos de datos exactos que se utilizan (lo que 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 con tipado dinámico, como Common Lisp, permiten declaraciones de tipos opcionales para la optimización por este motivo.

Por el contrario, la tipificación 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 tipados dinámicamente pueden resultar en menos comprobaciones para realizar y menos código para revisar. ^{[ aclaración necesaria ]} Esto también puede reducir el ciclo de edición-compilación-prueba-depuración.

Los lenguajes con tipado estático 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 utilizar un método o una 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 lenguaje puede tener tipado estático sin requerir declaraciones de tipos (los ejemplos incluyen Haskell , Scala , OCaml , F# , Swift y, en menor medida, C# y C++ ), por lo que la declaración explícita de tipos no es un requisito necesario para el tipado estático en todos los lenguajes.

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

La tipificación dinámica generalmente permite la tipificación de pato (que permite una reutilización más sencilla del código ). Muchos lenguajes ^{[ especificar ]} con tipificación estática también cuentan con tipificación de pato u otros mecanismos como la programación genérica que también permiten una reutilización más sencilla del código.

El tipado dinámico suele facilitar el uso de la metaprogramación . Por ejemplo, las plantillas de C++ suelen ser más complicadas 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 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 tipado estático. En algunos lenguajes, estas características 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. Estas construcciones avanzadas suelen proporcionarlas los lenguajes de programación dinámica ; muchos de ellos son de tipado dinámico, aunque el tipado dinámico no necesita estar relacionado con los lenguajes de programación dinámica .

Sistemas de tipo fuerte y débil

A menudo, coloquialmente, se hace referencia a los lenguajes como fuertemente tipados o débilmente tipados . 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 tipo 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 tipificadas. Los científicos informáticos utilizan el término lenguaje de tipo seguro para describir los lenguajes que no permiten operaciones o conversiones que violen las reglas del sistema de tipos.

Los científicos informáticos utilizan el término lenguaje seguro para la memoria (o simplemente lenguaje seguro ) para describir los lenguajes que no permiten que los programas accedan a la memoria que no se les ha asignado para su uso. Por ejemplo, un lenguaje seguro para la memoria comprobará los límites de la matriz o garantizará estáticamente (es decir, en tiempo de 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.

Consideremos el siguiente programa de un lenguaje que es seguro tanto en cuanto a tipos como en cuanto a memoria: ^[17]

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

En este ejemplo, la variable ztendrá el valor 42. Aunque puede que no sea lo que el programador esperaba, es un resultado bien definido. Si yfuera una cadena diferente, una que no se pudiera convertir a un número (por ejemplo, "Hola mundo"), el resultado también estaría bien definido. Tenga en cuenta que un programa puede ser seguro en cuanto a tipos o en cuanto a memoria y aun así fallar en una operación no válida. Esto es para lenguajes en los que 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 en cuanto a tipos, terminar el programa suele ser la única opción.

Consideremos ahora un ejemplo similar en C:

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

En este ejemplo, zse apuntará 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 a la que apunta y. Esta es una 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, en realidad podría imprimir cualquier byte que esté almacenado después de la cadena "37". Como muestra este ejemplo, C no es seguro para la memoria. Como se asumió que los datos arbitrarios eran un carácter, tampoco es un lenguaje seguro para los tipos.

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

Niveles variables de verificación de tipos

Algunos lenguajes permiten aplicar distintos niveles de verificación a distintas regiones del código. Algunos ejemplos son:

• La use strictdirectiva en JavaScript ^{[18] [19] [20]} y Perl aplica una comprobación más estricta.
• declare(strict_types=1)En PHP ^[21] , en cada archivo se permite que solo se acepte una variable del tipo exacto de la declaración de tipo, o se lanzará una.TypeError
• En VB.NET permite al compilador requerir una conversión entre objetos Option Strict On.

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

Sistemas de tipos opcionales

Gilad Bracha ha propuesto, principalmente , que la elección del sistema de tipos sea independiente de la elección del lenguaje; que un sistema de tipos debería ser un módulo que se pueda conectar a un lenguaje según sea necesario. Él cree que esto es ventajoso, porque lo que él llama sistemas de tipos obligatorios hacen 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 tipificación opcional está relacionada con la tipificación gradual , pero es distinta de ella . Si bien ambas disciplinas de tipificación se pueden utilizar para realizar análisis estáticos del 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) de actuar sobre valores de múltiples tipos, o a la capacidad de diferentes instancias de la misma estructura de datos de 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 planean usarla. Por esta razón, los científicos informáticos a veces llaman al uso de ciertas formas de polimorfismo programación genérica . Los fundamentos teóricos 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 sistemas de tipos especializados para su uso en determinados entornos con determinados 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 de tipos formales y solo están disponibles como parte de sistemas de investigación de prototipos.

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 abarcan los términos y los nombres abarcan los 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 en ; ${\displaystyle M}$ ${\displaystyle N}$
• ${\displaystyle \tau [\alpha :=\sigma ]}$(resp. ) describe el tipo que resulta de reemplazar todas las ocurrencias de la variable de tipo α (resp. término variable x ) en por el tipo σ (resp. término N ). ${\displaystyle \tau [x:=N]}$ ${\displaystyle \tau }$

1. También se denomina tipo de producto dependiente , ya que . ${\textstyle (x:\sigma )\to \tau =\prod _{x:\sigma }\tau }$
2. También conocido como tipo 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 una matriz. Podemos definir reglas de tipificación 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 los tipos dependientes convencionales es indecidible , no todos los programas que los utilizan pueden verificarse sin algún tipo de límite. 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 del lenguaje sea decidible, de modo que la verificación de tipos puede ser decidible. Sin embargo, en general, la prueba de decidibilidad es indecidible , por lo que muchos programas requieren anotaciones escritas a mano que pueden ser muy no triviales. Como esto impide el proceso de desarrollo, muchas implementaciones de lenguaje proporcionan 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 realizan verificación de tipos, 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 que tienen una y solo una referencia a ellos en todo momento. Estos son valiosos para describir valores inmutables grandes 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 "de manera interna" 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 sistema operativo prototipo Singularity para la comunicación entre procesos, lo que garantiza de forma estática que los procesos no puedan compartir objetos en la memoria compartida para evitar condiciones de carrera. El lenguaje Clean (un lenguaje similar a Haskell ) usa este sistema de tipos 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 ambos tipos dados con conjuntos de valores superpuestos. Por ejemplo, en la mayoría de las implementaciones de C, el rango del carácter con signo es de -128 a 127 y el rango del carácter sin signo es de 0 a 255, por lo que el rango del tipo de intersección de estos dos tipos sería de 0 a 127. Un tipo de intersección de este tipo se podría pasar de forma segura a funciones que esperan caracteres con signo 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 entero, y " float→ float" es el tipo de funciones que toman un argumento de punto flotante y devuelven un punto flotante, entonces la intersección de estos dos tipos se puede utilizar para describir funciones que hacen una u otra cosa, en función del tipo de entrada que se les proporciona. Una función de este tipo se podría pasar a otra función que espera una función " int→ int" de forma segura; simplemente no utilizaría la funcionalidad " float→ ".float

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

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

Tipos de uniones

Los tipos de unión son tipos que describen valores que pertenecen a cualquiera de dos tipos. Por ejemplo, en C, el char con signo tiene un rango de -128 a 127, y el char 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 se puede usar parcialmente dependiendo de qué miembro de la unión se acceda. Cualquier función que maneje este tipo de unión tendría que lidiar con números enteros en este rango completo. De manera más general, las únicas operaciones válidas en un tipo de unión son operaciones que son válidas en ambos tipos que se están uniendo. El concepto de "unión" de C es similar a los tipos de unión, pero no es seguro en cuanto a 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) no se conoce.

En una jerarquía de subclasificación, la unión de un tipo y un tipo antecesor (como su padre) es el tipo antecesor. La unión de tipos hermanos es un subtipo de su antecesor común (es decir, todas las operaciones permitidas en su antecesor 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 frecuentemente en conexión con los tipos de registro para representar módulos y tipos de datos abstractos , debido a su capacidad de 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:

• intT = { a: int; f: (int → entero); }
• floatT = { a: float; f: (float → int); }

Estos tipos son ambos 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 que el verificador de tipos infiera a qué tipo existencial pertenece un módulo determinado. 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:

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

Aunque los tipos de datos abstractos y los módulos se habían implementado en lenguajes de programación desde hacía 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 tipo existencial". ^{[25] 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.

Escritura gradual

En un sistema de tipos con tipado gradual , las variables pueden recibir un tipo en tiempo de compilación (que es tipado estático) o en tiempo de ejecución (que es tipado dinámico). ^[26] Esto permite a los desarrolladores de software elegir cualquiera de los paradigmas de tipos según sea apropiado, desde dentro de un solo lenguaje. ^[26] El tipado gradual utiliza un tipo especial llamado dinámico para representar tipos estáticamente desconocidos; el tipado 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 con un tipo específico. Otros, como el de Haskell, realizan inferencia de tipos : el compilador extrae 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 en 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 implicar, y a menudo lo hacen, un tipo en un contexto particular. Por ejemplo, una expresión 3.14puede implicar un tipo de punto flotante , mientras que puede implicar una lista de números 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 sistema de tipos dado, 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 una extensión, pero esto hace que la inferencia de tipos no sea computable. (Sin embargo, la comprobación de tipos es decidible y los programas de rango 1 aún 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 de tipos utilizando reglas de tipificación está naturalmente asociado con los problemas de decisión de verificación de tipos , tipabilidad y habitabilidad de tipos . ^[28]

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

Sistema de tipos 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 Object. Algunos lenguajes, como Java y Raku , tienen un tipo raíz pero también tienen tipos primitivos que no son objetos. ^[30] Java proporciona tipos de objetos contenedor que existen junto con los tipos primitivos para que los desarrolladores puedan usar los tipos de objetos contenedor o los tipos primitivos no objeto más simples. Raku convierte automáticamente los 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 coherente 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 coherencia, denominada 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. Por lo tanto, 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 lenguajes tienen diferentes criterios para determinar cuándo se entiende que dos expresiones de tipo denotan el mismo tipo. Estas diferentes teorías ecuacionales de tipos varían ampliamente; dos casos extremos son los sistemas de tipos estructurales , en los que dos tipos cualesquiera que describan 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 denotan 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 , entonces se puede usar Aun valor de type en un contexto donde se espera uno de type ( covariante ), incluso si lo inverso no es cierto. Al igual que la equivalencia, la relación de subtipos 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

Véase también

• Portal de programación informática

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

Notas

1. La línea de computadoras ALGOL de Burroughs determinaba 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. Solo el MCP (Programa de control maestro) podía escribir en los bits de código de bandera.
2. Por ejemplo, una abstracción con fugas podría surgir durante el desarrollo, lo que puede mostrar que se necesita más desarrollo de tipos. —"La evaluación de un programa bien tipado 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 un error 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. Pierce 2002, p. 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, p. 1: "El propósito fundamental de un sistema de tipos es evitar la ocurrencia de errores de ejecución durante la ejecución de un programa".
3. Pierce 2002, pág. 208.
4. Sethi, R. (1996). Lenguajes de programación: conceptos y construcciones (2.ª ed.). Addison-Wesley. pág. 142. ISBN 978-0-201-59065-4.OCLC 604732680  .
5. Nordström, 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. Oxford University Press. pág. 2. ISBN 978-0-19-154627-3.
6. Turner, DA (12 de junio de 2012). "Some History of Functional Programming Languages" (PDF) . Conferencia invitada en TFP12, en la Universidad de St Andrews . Véase la sección sobre Algol 60.
7. "... cualquier sistema de tipos válido y decidible debe ser incompleto" —D. Remy (2017). p. 29, Remy, 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. Pierce 2002.
9. Skeet, Jon (2019). C# en profundidad (4.ª ed.). Manning. ISBN 978-1617294532.
10. Miglani, Gaurav (2018). "Despacho dinámico de métodos o polimorfismo en tiempo de ejecución en Java". Archivado desde el original el 2020-12-07 . Consultado el 2021-03-28 .
11. Wright, Andrew K. (1995). Mecanografía práctica (PhD). Universidad Rice. hdl :1911/16900.
12. "dynamic (C# Reference)". Biblioteca MSDN . Microsoft . Consultado el 14 de enero de 2014 .
13. "std::any — Rust". doc.rust-lang.org . Consultado el 7 de julio de 2021 .
14. Meijer, Erik; Drayton, Peter. "Tipificación estática cuando es posible, tipificación dinámica cuando es necesaria: el fin de la guerra fría entre lenguajes de programación" (PDF) . Microsoft Corporation.
15. Laucher, Amanda; Snively, Paul (2012). "Tipos vs. pruebas". InfoQ.
16. Xi, Hongwei (1998). Tipos dependientes en programación práctica (PhD). Departamento de Ciencias Matemáticas, Universidad Carnegie Mellon. CiteSeerX 10.1.1.41.548 . 
    Xi, Hongwei; Pfenning, Frank (1999). "Tipos dependientes en la 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.S2CID245490  .​
17. Visual Basic es un ejemplo de un lenguaje que es seguro tanto en términos de tipos como de memoria.
18. "4.2.2 La variante estricta de ECMAScript". Especificación del lenguaje ECMAScript® 2020 (11.ª ed.). ECMA. Junio ​​de 2020. ECMA-262.
19. "Modo estricto – JavaScript". MDN . Developer.mozilla.org. 2013-07-03 . Consultado el 2013-07-17 .
20. "Modo estricto (JavaScript)". MSDN . Microsoft . Consultado el 17 de julio de 2013 .
21. "Tipificación estricta". Manual de PHP: Referencia del lenguaje: Funciones .
22. Bracha, G. "Tipos conectables" (PDF) .
23. "Claro. Se llama "tipado gradual" y yo lo calificaría como algo de moda..." ¿Existe algún lenguaje que permita tanto el tipado estático como el dinámico? . stackoverflow. 2012.
24. Kopylov, Alexei (2003). "Intersección dependiente: una nueva forma de definir registros en la teoría de tipos". 18.º Simposio IEEE sobre lógica en informática . LICS 2003. IEEE Computer Society. 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) . ACM Trans. Program. Lang. Syst . 10 (3): 470–502. doi :10.1145/44501.45065. S2CID  1222153.
26. Siek, Jeremy (24 de marzo de 2014). "¿Qué es la tipificación gradual?".
27. Siek, Jeremy; Taha, Walid (septiembre de 2006). Tipado gradual para lenguajes funcionales (PDF) . Scheme and Functional Programming 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. "Numéricos, § Auto-boxing". Documentación de Perl 6 .

Lectura adicional

• Cardelli, Luca ; Wegner, Peter (diciembre de 1985). "Sobre la comprensión de los tipos, la abstracción de datos y el polimorfismo" (PDF) . ACM Computing Surveys . 17 (4): 471–523. CiteSeerX  10.1.1.117.695 . doi :10.1145/6041.6042. S2CID  2921816.
• Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . MIT Press. ISBN 978-0-262-16209-8.
• Cardelli, Luca (2004). "Sistemas de tipos" (PDF) . En Allen B. Tucker (ed.). CRC Handbook of Computer Science and Engineering (2.ª ed.). CRC Press. ISBN 978-1584883609.
• Tratt, Laurence (julio de 2009). "5. Lenguajes de tipado dinámico". Advances in Computers . 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 Sistemas de tipos en Wikimedia Commons
• Smith, Chris (2011). "Qué hay que saber antes de debatir sobre sistemas de tipos".