En la teoría del lenguaje de programación , el subtipo (también llamado polimorfismo de subtipo o polimorfismo de inclusión ) es una forma de polimorfismo de tipo . Un subtipo es un tipo de datos que está relacionado con otro tipo de datos (el supertipo ) mediante alguna noción de sustituibilidad , lo que significa que los elementos del programa (típicamente subrutinas o funciones), escritos para operar sobre elementos del supertipo, también pueden operar sobre elementos del subtipo.
Si S es un subtipo de T, la relación de subtipo (escrita como S <: T , S ⊑ T , [1] o S ≤: T ) significa que cualquier término de tipo S puede usarse con seguridad en cualquier contexto donde un término de Se espera tipo T. La semántica precisa de la subtipificación aquí depende crucialmente de los detalles de cómo "se usará de manera segura" y "cualquier contexto" se define mediante un formalismo de tipo o lenguaje de programación determinado . El sistema de tipos de un lenguaje de programación esencialmente define su propia relación de subtipos, que bien puede ser trivial , si el lenguaje no admite (o admite muy pocos) mecanismos de conversión.
Debido a la relación de subtipos, un término puede pertenecer a más de un tipo. Por tanto, la subtipificación es una forma de polimorfismo de tipos. En la programación orientada a objetos el término 'polimorfismo' se utiliza comúnmente para referirse únicamente a este subtipo de polimorfismo , 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 de tipo simple ampliado con tipos de registros es quizás el entorno teórico más simple en el que se puede definir y estudiar una noción útil de subtipificación. [2] Debido a que el cálculo resultante permite que los términos tengan más de un tipo, ya no es una teoría de tipos "simple" . 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 subtipos proporcionan algunas de las características de la programación orientada a objetos. Normalmente, los lenguajes de programación funcionales también proporcionan alguna forma, generalmente restringida, de polimorfismo paramétrico. En un entorno teórico, es deseable estudiar la interacción de las dos características; un escenario teórico común es el sistema F <: . Del sistema F <: se pueden derivar varios cálculos que intentan capturar las propiedades teóricas de la programación orientada a objetos .
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 lenguajes orientados a objetos; [3] 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 que surge de una característica del lenguaje que permite crear nuevos objetos a partir de los existentes. En varios lenguajes orientados a objetos, la subtipificación se denomina herencia de interfaz , y la herencia se denomina herencia de implementación .
La noción de subtipos 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 la subtipificación los dieron John C. Reynolds en 1980, quien utilizó la teoría de categorías para formalizar conversiones implícitas , y Luca Cardelli (1985). [4]
El concepto de subtipos ha ganado visibilidad (y sinonimia con 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 subtipado definido por Liskov y Jeannette Wing , llamado subtipo conductual 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 detalles).
En el diagrama se muestra un ejemplo práctico sencillo de subtipos. El tipo "pájaro" tiene tres subtipos "pato", "cuco" y "avestruz". Conceptualmente, cada uno de ellos es una variedad del tipo básico "pájaro" que hereda muchas características de "pájaro" 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 ejemplo más práctico, un lenguaje podría permitir el uso de valores enteros siempre que se esperen valores de punto flotante ( Integer<: Float), o podría definir un tipo genérico.Númerocomo un supertipo común de números enteros y reales. En este segundo caso, solo tenemos Integer<: Numbery Float<: Number, pero Integery Floatno 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:
la función max ( x como número , y como número ) es si x < y entonces devuelve y; de lo contrario, devuelve x final Si entero y real son subtipos de Numbery 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 un operador de este tipo limita en gran medida el tipo de 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. Reescribir esta función para que solo acepte 'x' e 'y' del mismo tipo requiere polimorfismo acotado .
En teoría de tipos , el concepto de subsunción [5] 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 extensivamente enumerando todos los valores, o se puede describir intencionalmente estableciendo la pertenencia del conjunto por un predicado sobre un dominio de valores posibles. En los lenguajes de programación comunes, los tipos de enumeración se definen extensivamente 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 información de tipo, como un prototipo para copiar o ampliar.
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 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". [ cita necesaria ]
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 relevancia del subtipo (el número de situaciones en las que puede aceptarse o introducirse), en comparación con sus supertipos "más generales". La desventaja de tener esta información más detallada es que representa elecciones incorporadas que reducen la prevalencia del subtipo (el número de situaciones que pueden generarlo o producirlo).
En el contexto de la subsunción, las definiciones de tipos se pueden expresar utilizando la notación constructora 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: "¿un valor entero es mayor o igual a 100 y menor que 200?". Si un valor coincide con los criterios, la función devuelve el valor. De lo contrario, el valor no se selecciona y no se devuelve nada. (Las listas por comprensión son una forma de este patrón que se utiliza en muchos lenguajes de programación).
Si hay dos predicados, que aplican criterios de selección para el tipo T y que aplican criterios adicionales para el tipo S , entonces se pueden definir conjuntos para los dos tipos:
El predicado se aplica junto con el predicado compuesto S que define S. Los dos predicados están unidos , por lo que ambos deben ser verdaderos para que se seleccione un valor. El predicado subsume el predicado T , por lo que S <: T .
Por ejemplo: existe una subfamilia de especies de felinos 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.
La conjunción de predicados se ha expresado aquí mediante la aplicación del segundo predicado sobre el dominio de valores que conforman el primer predicado. Vistos como tipos, Felis <: Felinae <: Felidae .
Si T subsume S ( T :> S ), entonces un procedimiento, función o expresión dado un valor como operando (valor de parámetro o término) podrá operar sobre ese valor como uno de tipo T , porque . En el ejemplo anterior, podríamos esperar que la función de Subfamilia sea aplicable a valores de los tres tipos Felidae , Felinae y Felis .
Los teóricos de tipos hacen una distinción entre subtipos nominales , en los que sólo 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. El subtipo orientado a objetos basado en clases descrito anteriormente es nominal; Una regla de subtipo 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 independientemente de que uno herede del otro. Este llamado tipeo pato es común en lenguajes orientados a objetos de tipado dinámico. También son bien conocidas reglas sólidas de subtipificación estructural para tipos distintos de los tipos de objetos. [ cita necesaria ]
Las implementaciones de lenguajes de programación con subtipos 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 subclases en un lenguaje orientado a objetos suele ser inclusiva; Las relaciones de subtipificación que relacionan números enteros y 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 subtipos, es reflexiva (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 por tipos.
Los tipos de registros dan lugar a los conceptos de subtipificación de ancho y profundidad . Estos expresan dos formas diferentes de obtener un nuevo tipo de registro que permita 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 el tipo original admitido.
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 de ancho aparecerá en el subtipo de ancho. Por tanto, cualquier operación factible en el supertipo será compatible con 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 también lo es para su subtipo, cualquier operación factible en el supertipo de registro está admitida por el subtipo de registro. La subtipificación de profundidad solo tiene sentido para registros inmutables: por ejemplo, puede asignar 1,5 al campo 'x' de un punto real (un registro con dos campos reales), pero no puede hacer lo mismo con el campo 'x' de un punto entero (que, sin embargo, es un subtipo profundo del tipo 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 polimorfismo paramétrico con subtipificación de tipos de registros y es una base teórica para muchos lenguajes de programación funcionales que admiten ambas características.
Algunos sistemas también admiten la subtipificación 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.
Si T 1 → T 2 es un tipo de función, entonces un subtipo del mismo es cualquier tipo de función S 1 → S 2 con la propiedad de que T 1 <: S 1 y S 2 <: T 2 . Esto se puede resumir utilizando la siguiente regla de escritura :
Se dice que el tipo de parámetro de S 1 → S 2 es contravariante porque la relación de subtipo se invierte, mientras que el tipo de retorno es covariante . Informalmente, esta inversión se produce porque el tipo refinado es "más liberal" en los tipos que acepta y "más conservador" en los tipos que devuelve. Esto es lo que funciona exactamente en Scala : una función n -aria es internamente una clase que hereda el rasgo (que puede verse como una interfaz general en lenguajes tipo Java ), donde están los tipos de parámetros y 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 pueda usarse de manera segura en el contexto de otra. El trabajo de Liskov en esta área se centró en la subtipificación conductual , que además de la seguridad del sistema de tipos discutida en este artículo también requiere que los subtipos preserven todas las invariantes garantizadas por los supertipos en algún contrato . [6] Esta definición de subtipo es generalmente indecidible , por lo que no puede ser verificada por un verificador de tipos .
La subtipificación de referencias mutables es similar al tratamiento de valores de parámetros y valores de retorno. Las referencias de solo escritura (o receptores ) son contravariantes, como los valores de los parámetros; Las referencias de solo lectura (o fuentes ) son covariantes, como los valores de retorno. Las referencias mutables que actúan como fuentes y sumideros son invariantes.
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 , son posibles todas las combinaciones de subtipificación y herencia:
El primer caso se ilustra con tipos independientes, como Booleany Float.
El segundo caso puede ilustrarse mediante la relación entre Int32y Int64. En la mayoría de los lenguajes de programación orientados a objetos, Int64no están relacionados por herencia con Int32. Sin embargo, Int32puede considerarse un subtipo de, Int64ya que cualquier valor entero de 32 bits puede convertirse en un valor entero de 64 bits.
El tercer caso es una consecuencia de la contravarianza de entrada de subtipificación de funciones . 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 una clase derivada tipo S de T . Por herencia, el tipo de m en S es S → S . [ cita necesaria ] Para que S sea un subtipo de T, el tipo de m en S debe ser un subtipo del tipo de m en T [ cita necesaria ] , 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 , lo cual 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. [3]
En los sistemas de subtipos coercitivos, los subtipos se definen mediante funciones de conversión de tipos implícitas de subtipo a supertipo. Para cada relación de subtipo ( S <: T ), se proporciona una función de coerción coerce : S → T , y cualquier objeto s de tipo S se considera como el objeto coerce 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 ( coaccionar T → U ∘ coaccionar S → T ). La coerción de tipo de un tipo para coaccionar a sí mismo T → T es la función de identidad id T .
Las funciones de coerción para registros y subtipos de unión disjuntos 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 tipos de funciones puede estar dada por f' ( t ) = coaccionar S 2 → T 2 ( f ( coaccionar T 1 → S 1 ( t ))), lo que refleja la contravarianza de los valores de los parámetros y la covarianza de los valores de retorno.
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 subtipos, se debe tener cuidado de garantizar que todas las coerciones de tipo sean coherentes. Por ejemplo, si un número entero como 2 : int se puede convertir en un número de coma flotante (digamos, 2.0 : float ), entonces no es admisible convertir 2.1 : float en 2 : int , porque la coerción compuesta coerce float → float dado por coerce int → float ∘ coerce float → int entonces sería distinto de la identidad coercion id float .
Libros de texto
Documentos
