Subtipado

En la teoría del lenguaje de programación, la subtipificación (también polimorfismo de subtipo o polimorfismo de inclusión) es una forma de polimorfismo de tipos en la que un subtipo es un tipo de datos que está relacionado con otro tipo de datos (el supertipo) por alguna noción de sustituibilidad, lo que significa que los elementos del programa, típicamente subrutinas o funciones, escritos para operar en elementos del supertipo pueden también operan sobre elementos del subtipo. Si S es un subtipo de T, la relación de subtipificación (escrita como S <: T, S ⊑ T, o S ≤: T) significa que cualquier término de tipo S se puede utilizar con seguridad en cualquier contexto donde se espera un término de tipo T. La semántica precisa de la subtipificación aquí depende de manera crucial de los detalles de cómo "se usará con seguridad" y "cualquier contexto" están definidos por un determinado tipo de formalismo o lenguaje de programación. El sistema de tipos de un lenguaje de programación define esencialmente su propia relación de subtipificación, que bien puede ser trivial, si el lenguaje no admite (o admite muy pocos) mecanismos de conversión.

Debido a la relación de subtipificación, un término puede pertenecer a más de un tipo. La subtipificación es, por lo tanto, una forma de polimorfismo de tipos. En la programación orientada a objetos, el término 'polimorfismo' se usa comúnmente para referirse únicamente a este polimorfismo de subtipo, mientras que las técnicas de polimorfismo paramétrico se considerarían programación genérica.

Los lenguajes de programación funcionales a menudo permiten la subtipificación de registros. En consecuencia, el cálculo lambda simplemente tipificado ampliado con tipos de registro es quizás el marco teórico más simple en el que se puede definir y estudiar una noción útil de subtipificación. Debido a que el cálculo resultante permite que los términos tengan más de un tipo, ya no es un cálculo "simple" teoría de tipos. Dado que los lenguajes de programación funcional, por definición, admiten literales de funciones, que también se pueden almacenar en registros, los tipos de registros con subtipificación brindan algunas de las características de la programación orientada a objetos. Por lo general, los lenguajes de programación funcional también proporcionan alguna forma, generalmente restringida, de polimorfismo paramétrico. En un marco teórico, es deseable estudiar la interacción de las dos características; un escenario teórico común es el sistema F<:. Varios cálculos que intentan capturar las propiedades teóricas de la programación orientada a objetos pueden derivarse del sistema F_<:.

El concepto de subtipificación está relacionado con las nociones lingüísticas de hiponimia y holonimia. También está relacionado con el concepto de cuantificación acotada en lógica matemática (ver Lógica ordenada por orden). La subtipificación no debe confundirse con la noción de herencia (clase u objeto) de los lenguajes orientados a objetos; la subtipificación es una relación entre tipos (interfaces en el lenguaje orientado a objetos) mientras que la herencia es una relación entre implementaciones derivada de una característica del lenguaje que permite crear nuevos objetos a partir de los existentes. En una serie de lenguajes orientados a objetos, la creación de subtipos se denomina herencia de interfaz, y la herencia se denomina herencia de implementación.

Orígenes

La noción de subtipado en los lenguajes de programación se remonta a la década de 1960; se introdujo en los derivados de Simula. Los primeros tratamientos formales de subtipificación fueron realizados por John C. Reynolds en 1980, quien usó la teoría de categorías para formalizar conversiones implícitas, y Luca Cardelli (1985).

El concepto de creación de subtipos ha ganado visibilidad (y sinónimo de polimorfismo en algunos círculos) con la adopción generalizada de la programación orientada a objetos. En este contexto, el principio de sustitución segura a menudo se denomina principio de sustitución de Liskov, en honor a Barbara Liskov, quien lo popularizó en un discurso de apertura en una conferencia sobre programación orientada a objetos en 1987. Debido a que debe considerar objetos mutables, la noción ideal de creación de subtipos definido por Liskov y Jeannette Wing, llamado subtipado de comportamiento es considerablemente más fuerte que lo que se puede implementar en un verificador de tipos. (Consulte § Tipos de funciones a continuación para obtener más información).

Ejemplos

Ejemplo de subtipos: donde el pájaro es el supertipo y todos los demás son subtipos como denotado por la flecha en la notación UML

En el diagrama se muestra un ejemplo práctico simple de subtipos. El tipo "pájaro" tiene tres subtipos "pato", "cuco" y "avestruz". Conceptualmente, cada uno de estos es una variedad del tipo básico "pájaro" que hereda muchos "pájaros" características pero tiene algunas diferencias específicas. En este diagrama se utiliza la notación UML, con flechas abiertas que muestran la dirección y el tipo de relación entre el supertipo y sus subtipos.

Como un ejemplo más práctico, un lenguaje podría permitir que se usen valores enteros donde se esperan valores de coma flotante (Integer <: Float), o podría definir un tipo genérico Number como supertipo común de enteros y reales. En este segundo caso, solo tenemos Integer <: Number y Float <: Number, pero Integer y Float no son subtipos entre sí.

Los programadores pueden aprovechar la subtipificación para escribir código de una manera más abstracta de lo que sería posible sin ella. Considere el siguiente ejemplo:

función max ()x como Número, Sí. como Número) es si x . Sí. entonces retorno Sí. más retorno xfinal

Si entero y real son ambos subtipos de Number, y se define un operador de comparación con un Número arbitrario para ambos tipos, entonces se pueden pasar valores de cualquier tipo a esta función. Sin embargo, la posibilidad misma de implementar dicho operador restringe en gran medida el tipo Número (por ejemplo, no se puede comparar un número entero con un número complejo), y en realidad solo tiene sentido comparar números enteros con números enteros y reales con reales. Reescribiendo esta función para que solo acepte 'x' y 'y' del mismo tipo requiere polimorfismo acotado.

Subsunción

En teoría de tipos, el concepto de subsunción se utiliza para definir o evaluar si un tipo S es un subtipo de tipo T.

Un tipo es un conjunto de valores. El conjunto se puede describir extensionalmente enumerando todos los valores, o se puede describir intencionalmente indicando la pertenencia al conjunto mediante un predicado sobre un dominio de valores posibles. En los lenguajes de programación comunes, los tipos de enumeración se definen de manera extensiva enumerando valores. Los tipos definidos por el usuario, como registros (estructuras, interfaces) o clases, se definen intencionalmente mediante una declaración de tipo explícita o mediante el uso de un valor existente, que codifica la información de tipo, como prototipo para ser copiado o ampliado.

Al discutir el concepto de subsunción, el conjunto de valores de un tipo se indica escribiendo su nombre en cursiva matemática: T. El tipo, visto como un predicado sobre un dominio, se indica escribiendo su nombre en negrita: T. El símbolo convencional <: significa "es un subtipo de", y :> significa "es un supertipo de".

• Tipo T subsumos S si el conjunto de valores T que define, es un superset del conjunto S, para que cada miembro de S es también miembro de T.
• Un tipo puede ser subsumido por más de un tipo: los supertipos S intersección en S.
• Si S. T (y por lo tanto) S ⊆ T ), entonces T, el predicado que circunscribe el conjunto T, debe ser parte del predicado S (sobre el mismo dominio) que define S.
• Si S subsumos T, y T subsumos S, entonces los dos tipos son iguales (aunque pueden no ser del mismo tipo si el sistema de tipo distingue tipos por nombre).

En términos de especificidad de la información, un subtipo se considera más específico que cualquiera de sus supertipos, porque contiene al menos tanta información como cada uno de ellos. Esto puede aumentar la aplicabilidad o la relevancia del subtipo (el número de situaciones en las que puede aceptarse o introducirse), en comparación con su "más general" supertipos La desventaja de tener esta información más detallada es que representa opciones incorporadas que reducen la prevalencia del subtipo (el número de situaciones que son capaces de generarlo o producirlo).

En el contexto de la subsunción, las definiciones de tipo se pueden expresar mediante la notación de creación de conjuntos, que utiliza un predicado para definir un conjunto. Los predicados se pueden definir sobre un dominio (conjunto de valores posibles) D. Los predicados son funciones parciales que comparan valores con criterios de selección. Por ejemplo: "¿es un valor entero mayor o igual que 100 y menor que 200?". Si un valor coincide con los criterios, la función devuelve el valor. Si no, el valor no se selecciona y no se devuelve nada. (Las listas de comprensión son una forma de este patrón que se usa en muchos lenguajes de programación).

Si hay dos predicados, PT{displaystyle P_{T} que aplica criterios de selección para el tipo T, y Ps{displaystyle P_{s} que aplica criterios adicionales para el tipo S, entonces se pueden definir conjuntos para los dos tipos:

T={}v▪ ▪ D▪ ▪ PT()v)}{displaystyle T={vin Dmid P_{T}(v)}

S={}v▪ ▪ D▪ ▪ PT()v)yPs()v)}{displaystyle S={vin Dmid P_{T}(v){text{ and }P_{s}(v)}

El predicado T=PT{displaystyle mathbf {T} =P_{T} se aplica junto con Ps{displaystyle P_{s} como parte del complejo predicado S Definición S. Los dos predicados son conjoined, así que ambos deben ser verdaderos para que un valor sea seleccionado. El predicado S=T∧ ∧ Ps=PT∧ ∧ Ps{displaystyle mathbf {S} =mathbf {T} land P_{s}=P_{T}land P_{s} subsume el predicado TAsí que S. T.

Por ejemplo: existe una subfamilia de especies de gatos llamada Felinae, que forma parte de la familia Felidae. El género Felis, al que pertenece la especie de gato doméstico Felis catus, forma parte de esa subfamilia.

Felinae={}cat▪ ▪ Felidae▪ ▪ ofSubfamilSí.()cat,felinaeSubfamilSí.Name)}{displaystyle {matit {Felinae={catin Felidaemid ofSubfamily(cat,felinaeSubfamilyName)}}}}}

Felis={}cat▪ ▪ Felinae▪ ▪ ofGenus()cat,felisGenusName)}{displaystyle {matit {Felis={catin Felinaemid ofGenus(cat,felisGenusName)}}}}}}}

La conjunción de predicados se ha expresado aquí mediante la aplicación del segundo predicado sobre el dominio de valores conforme al primer predicado. Vistos como tipos, Felis <: Felinae <: Felidae.

Si T subsumos S ()T: titulado S) entonces un procedimiento, función o expresión dado un valor s▪ ▪ S{displaystyle sin S} como un operario (valor o término del parámetro) será capaz de operar sobre ese valor como uno de tipo T, porque s▪ ▪ T{displaystyle sin T}. En el ejemplo anterior, podríamos esperar la función ofSubfamily para ser aplicable a los valores de los tres tipos Felidae, Felinae y Felis.

Esquemas de subtipificación

Los teóricos de tipos distinguen entre subtipos nominales, en los que solo los tipos declarados de cierta manera pueden ser subtipos entre sí, y subtipos estructurales, en los que la estructura de dos tipos determina si uno es o no un subtipo del otro. La subtipificación orientada a objetos basada en clases descrita anteriormente es nominal; una regla de subtipado estructural para un lenguaje orientado a objetos podría decir que si los objetos de tipo A pueden manejar todos los mensajes que los objetos de tipo B pueden manejar (es decir, si definen todos los mismos métodos), entonces A es un subtipo de B sin importar si alguno hereda del otro. Este llamado tipo de pato es común en lenguajes orientados a objetos de tipo dinámico. También se conocen bien las reglas sólidas de subtipificación estructural para tipos distintos de los tipos de objetos.

Las implementaciones de lenguajes de programación con subtipificación se dividen en dos clases generales: implementaciones inclusivas, en las que la representación de cualquier valor de tipo A también representa el mismo valor en el tipo B si A <: B, e implementaciones coercitivas, en las que un valor de tipo A se puede convertir automáticamente en uno de tipo B. La subtipificación inducida por la subclasificación en un lenguaje orientado a objetos suele ser inclusiva; Las relaciones de subtipificación que relacionan números enteros y números de punto flotante, que se representan de manera diferente, suelen ser coercitivas.

En casi todos los sistemas de tipos que definen una relación de subtipificación, es reflexivo (es decir, A <: A para cualquier tipo A) y transitiva (lo que significa que si A <: B y B <: C entonces A <: C). Esto lo convierte en un pedido anticipado de tipos.

Tipos de registros

Subtipos de ancho y profundidad

Los tipos de registros dan lugar a los conceptos de ancho y profundidad de subtipos. Estos expresan dos formas diferentes de obtener un nuevo tipo de registro que permite las mismas operaciones que el tipo de registro original.

Recuerde que un registro es una colección de campos (con nombre). Dado que un subtipo es un tipo que permite todas las operaciones permitidas en el tipo original, un subtipo de registro debe admitir las mismas operaciones en los campos que admitía el tipo original.

Un tipo de forma de lograr dicho soporte, llamado subtipo de ancho, agrega más campos al registro. Más formalmente, cada campo (con nombre) que aparece en el supertipo ancho aparecerá en el subtipo ancho. Así, cualquier operación factible sobre el supertipo será soportada por el subtipo.

El segundo método, llamado subtipo de profundidad, reemplaza los distintos campos con sus subtipos. Es decir, los campos del subtipo son subtipos de los campos del supertipo. Dado que cualquier operación admitida para un campo en el supertipo es compatible con su subtipo, cualquier operación factible en el supertipo de registro es compatible con el subtipo de registro. La subtipificación de profundidad solo tiene sentido para registros inmutables: por ejemplo, puede asignar 1,5 a la 'x' campo de un punto real (un registro con dos campos reales), pero no se puede hacer lo mismo con la 'x' campo de un punto entero (que, sin embargo, es un subtipo profundo del tipo de punto real) porque 1.5 no es un número entero (ver Varianza).

La subtipificación de registros se puede definir en System F<:, que combina el polimorfismo paramétrico con la subtipificación de tipos de registro y es una base teórica para muchos lenguajes de programación funcionales que admiten ambas funciones.

Algunos sistemas también admiten la creación de subtipos de tipos de unión disjuntos etiquetados (como los tipos de datos algebraicos). La regla para el subtipo de ancho se invierte: cada etiqueta que aparece en el subtipo de ancho debe aparecer en el supertipo de ancho.

Tipos de funciones

Si T₁ → T₂ es un tipo de función, entonces un subtipo es cualquier tipo de función S₁ → S₂ con la propiedad que T₁ <: S ₁ y S₂ <: T₂. Esto se puede resumir usando la siguiente regla de escritura:

T1≤ ≤:S1S2≤ ≤:T2S1→ → S2≤ ≤:T1→ → T2{displaystyle {T_{1}leq:S_{1}quad S_{2}leq:T_{2} over {S_{1}rightarrow S_{2}leq:T_{1}rightarrow T_{2}}}

El tipo de parámetro S₁ → S₂ se dice que es contravariante porque la relación subtítulos se invierte para ella, mientras que el tipo de retorno es covariante. Informalmente, esta inversión ocurre porque el tipo refinado es "más liberal" en los tipos que acepta y "más conservador" en el tipo que regresa. Esto es exactamente lo que funciona en Scala: a n- la función diaria es internamente una clase que hereda la FunctionN()− − A1,− − A2,...... ,− − An,+B){displaystyle {mathtt {fn}({-A_{1},{-A_{2}},dots{-A_{n}}}}}}}}}} rasgo (que se puede ver como una interfaz general en lenguajes similares a Java), donde A1,A2,...... ,An{displaystyle {mathtt {A_{1},A_{2},dots A_{n}}} son los tipos de parámetro, y B{displaystyle {Mathtt {B}} es su tipo de retorno; "−" antes del tipo significa que el tipo es contravariante mientras que "+" significa covariante.

En los lenguajes que permiten efectos secundarios, como la mayoría de los lenguajes orientados a objetos, la subtipificación generalmente no es suficiente para garantizar que una función se pueda usar de manera segura en el contexto de otra. El trabajo de Liskov en esta área se centró en la subtipificación del comportamiento, que además de la seguridad del sistema de tipos discutida en este artículo también requiere que los subtipos conserven todas las invariantes garantizadas por los supertipos en algún contrato. Esta definición de subtipado generalmente es indecidible, por lo que no puede ser verificada por un verificador de tipos.

La creación de subtipos de referencias mutables es similar al tratamiento de valores de parámetros y valores devueltos. Las referencias de solo escritura (o sumideros) son contravariantes, como los valores de los parámetros; las referencias de solo lectura (o fuentes) son covariantes, como los valores devueltos. Las referencias mutables que actúan como fuentes y sumideros son invariables.

Relación con la herencia

La subtipificación y la herencia son relaciones independientes (ortogonales). Pueden coincidir, pero ninguno es un caso especial del otro. En otras palabras, entre dos tipos S y T, todas las combinaciones de subtipado y herencia son posibles:

1. S no es un subtipo ni un tipo derivado T
2. S es un subtipo pero no es un tipo derivado T
3. S no es un subtipo pero es un tipo derivado T
4. S es un subtipo y un tipo derivado T

El primer caso se ilustra con tipos independientes, como Boolean y Float.

El segundo caso se puede ilustrar con la relación entre Int32 y Int64. En la mayoría de los lenguajes de programación orientados a objetos, Int64 no están relacionados por herencia con Int32. Sin embargo, Int32 puede considerarse un subtipo de Int64, ya que cualquier valor entero de 32 bits puede convertirse en un valor entero de 64 bits.

El tercer caso es una consecuencia de la función de subtipificación de la contravarianza de entrada. Supongamos una superclase de tipo T que tiene un método m que devuelve un objeto del mismo tipo (es decir, el tipo de m es T → T, también tenga en cuenta que el primer parámetro de m es this/self) y un tipo de clase derivada S de T. Por herencia, el tipo de m en S es S → S. Para que S sea un subtipo de T el tipo de m en S debe ser un subtipo de la tipo de m en T, en otras palabras: S → S ≤: T → T. Mediante la aplicación ascendente de la regla de subtipificación de funciones, esto significa: S ≤: T y T ≤: S, que solo es posible si S y T son iguales. Dado que la herencia es una relación irreflexiva, S no puede ser un subtipo de T.

Los subtipos y la herencia son compatibles cuando todos los campos y métodos heredados del tipo derivado tienen tipos que son subtipos de los campos y métodos correspondientes del tipo heredado.

Coacciones

En los sistemas de subtipado coercitivo, los subtipos se definen mediante funciones de conversión de tipo implícitas de subtipo a supertipo. Para cada relación de subtipificación (S <: T), una función de coerción coerce: S → Se proporciona T, y cualquier objeto s de tipo S se considera el objeto coaccionar_{S → T}(s) de tipo T. Una función de coerción puede definirse por composición: si S <: T y T <: U entonces s puede considerarse como un objeto de tipo u bajo la coerción compuesta (coerce_{T → U} ∘ coaccionar_{S → T}). La coerción de tipo de un tipo a sí mismo coerce_{T → T} es la función de identidad id_T.

Las funciones de coerción para registros y subtipos de unión disjunta se pueden definir por componentes; en el caso de registros de ancho extendido, la coerción de tipos simplemente descarta cualquier componente que no esté definido en el supertipo. La coerción de tipo para los tipos de función puede ser dada por f'(s) = coerce_{S2 → T2}(f(coaccionar<sub T₁ → S₁(t))), que refleja la contravarianza de los valores de los parámetros y la covarianza de los valores devueltos.

La función de coerción se determina de forma única dado el subtipo y el supertipo. Por lo tanto, cuando se definen múltiples relaciones de subtipificación, se debe tener cuidado para garantizar que todas las coacciones de tipo sean coherentes. Por ejemplo, si un número entero como 2: int se puede forzar a un número de punto flotante (por ejemplo, 2.0: float), entonces no es admisible forzar 2.1: float a 2: int, porque la coerción compuesta coerce_{float → float} dado por coaccionar_{int → float} ∘ coaccionar_{float → int} sería entonces distinto de la coerción de identidad id_float .