Subtipificación

En la teoría de los lenguajes de programación , el subtipo (también llamado polimorfismo de subtipo o polimorfismo de inclusión ) es una forma de polimorfismo de tipos . 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 (normalmente 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 subtipificación (escrita como $S <: T$ , $S ⊑ T$ , ^[1] o $S \leq: T$ ) significa que cualquier término de tipo S puede usarse con seguridad en cualquier contexto donde se espera un término de tipo T. La semántica precisa de la subtipificación aquí depende crucialmente de los detalles de cómo se define "utilización segura" y "cualquier contexto" en un formalismo de tipos o lenguaje de programación determinado . 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 mecanismos de conversión (o admite muy pocos).

Debido a la relación de subtipificación, un término puede pertenecer a más de un tipo. La subtipificación es, por tanto, una forma de polimorfismo de tipos. En la programación orientada a objetos, el término "polimorfismo" se utiliza habitualmente 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 funcional a menudo permiten la subtipificación de registros . En consecuencia, el cálculo lambda de tipos simples extendido 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 función , que también se pueden almacenar en registros, los tipos de registros con subtipificación proporcionan 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 entorno teórico, es deseable estudiar la interacción de las dos características; un entorno 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 se pueden derivar 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 (véase Lógica ordenada por orden ). La subtipificación no debe confundirse con la noción de herencia (de clase u objeto) de los 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 se derivan 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 .

Orígenes

El concepto de subtipificación en los lenguajes de programación se remonta a la década de 1960; se introdujo en las derivadas de Simula . Los primeros tratamientos formales de la subtipificación fueron dados por John C. Reynolds en 1980, quien utilizó la teoría de categorías para formalizar las conversiones implícitas , y por Luca Cardelli (1985). ^[4]

El concepto de subtipificación 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 subtipificación definida por Liskov y Jeannette Wing , llamada subtipificación conductual , es considerablemente más sólida que lo que se puede implementar en un verificador de tipos . (Consulte § Tipos de función a continuación para obtener más detalles).

Ejemplos

Ejemplo de subtipos: donde bird es el supertipo y todos los demás son subtipos, como lo indica la flecha en la notación UML

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 de punta abierta 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 que se utilicen valores enteros dondequiera que se esperen valores de punto flotante ( Integer<: Float), o podría definir un tipo genéricoNúmerocomo un supertipo común de los números enteros y los 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:

función max ( x como Número , y como Número ) es si x < y entonces devuelve y de lo contrario devuelve x fin

Si tanto un entero como un real son 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 cualquiera de los dos tipos a esta función. Sin embargo, la posibilidad misma de implementar un operador de este tipo restringe en gran medida el tipo de número (por ejemplo, no se puede comparar un entero con un número complejo) y, en realidad, solo tiene sentido comparar enteros con enteros y reales con reales. Reescribir esta función para que solo acepte 'x' e 'y' del mismo tipo requiere polimorfismo acotado .

Subsunción

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

Un tipo es un conjunto de valores. El conjunto se puede describir de forma extensional enumerando todos los valores, o se puede describir de forma intencional 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 forma extensional enumerando valores. Los tipos definidos por el usuario, como los registros (estructuras, interfaces) o las clases, se definen de forma intencional 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 analizar 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". ^{[ cita requerida ]}

Un tipo T subsume S si el conjunto de valores $T$ que define es un superconjunto del conjunto $S$ , de modo que cada miembro de $S$ es también un miembro de $T$ .
Un tipo puede ser subsumido por más de un tipo: los supertipos de S se intersecan en $S$ .
Si S <: T (y por lo tanto $S \subseteq 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 subsume a T , y T subsume a S , entonces los dos tipos son iguales (aunque pueden no ser el mismo tipo si el sistema de tipos distingue los 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 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 tipo se pueden expresar utilizando la notación de generador 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. Si no, 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, uno que aplica criterios de selección para el tipo T y otro que aplica criterios adicionales para el tipo S , entonces se pueden definir conjuntos para los dos tipos: $Estilo de visualización P_{T}$ $P_{s}$

T=\{v\en D\mid \ P_{T}(v)\}

S=\{v\en D\mid \ P_{T}(v){\text{ y }}P_{s}(v)\}

El predicado se aplica junto con el predicado compuesto S que define $a 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 . $\mathbf {T} = P_{T}$ $P_{s}$ $\mathbf {S} =\mathbf {T} \land P_{s}=P_{T}\land P_{s}$

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.

{\mathit {Felinae=\{cat\in Felidae\mid \ ofSubfamily(cat,felinaeSubfamilyName)\}}}

{\mathit {Felis=\{cat\in Felinae\mid \ 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 subsume S ( T :> S ) entonces un procedimiento, función o expresión que reciba 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 deSubfamilia fuera aplicable a valores de los tres tipos Felidae , Felinae y Felis . $s\en S$ $s\en T$

Esquemas de subtipificación

Los teóricos de tipos distinguen entre subtipos nominales , en los que sólo los tipos declarados de una determinada 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 si alguno hereda del otro. Este llamado tipado de pato es común en lenguajes orientados a objetos de tipado dinámico. También se conocen bien reglas de subtipo estructural sólidas para tipos distintos de los tipos de objeto. ^{[ cita requerida ]}

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 de punto flotante, que se representan de forma diferente, suelen ser coercitivas.

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

Tipos de registros

Subtipificación de ancho y profundidad

Los tipos de registros dan lugar a los conceptos de subtipificación por ancho y profundidad , que 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.

Una forma de lograr dicho soporte, denominada subtipificación de ancho , agrega más campos al registro. De manera más formal, cada campo (nombrado) que aparece en el supertipo de ancho aparecerá en el subtipo de ancho. Por lo tanto, cualquier operación factible en el supertipo será admitida por el subtipo.

El segundo método, llamado subtipado en profundidad , reemplaza los distintos campos por 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 admitida para su subtipo, cualquier operación factible en el supertipo de registro es admitida por el subtipo de registro. El subtipado en 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 de punto real) porque 1,5 no es un entero (consulte 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 registros y es una base teórica para muchos lenguajes de programación funcional 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 la subtipificación del ancho se invierte: cada etiqueta que aparece en el subtipo de ancho debe aparecer en el supertipo de ancho.

Tipos de funciones

Si $T 1 \to T 2$ es un tipo de función, entonces un subtipo de este es cualquier tipo de función $S 1 \to 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 tipificación :

${T_{1}\leq :S_{1}\quad S_{2}\leq :T_{2}} \sobre {S_{1}\rightarrow S_{2}\leq :T_{1}\rightarrow T_{2}}$

Se dice que el tipo de parámetro de $S 1 \to S 2$ es contravariante porque la relación de subtipificación se invierte para él, mientras que el tipo de retorno es covariante . De manera informal, 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 devuelve. Esto es exactamente lo que funciona 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 son los tipos de parámetros y es su tipo de retorno; "−" antes del tipo significa que el tipo es contravariante mientras que "+" significa covariante. ${\mathtt {Función_{N}({-A_{1}},{-A_{2}},\puntos ,{-A_{n}},{+B})}}$ ${\mathtt {A_{1},A_{2},\puntos ,A_{n}}}$ ${\mathtt {B}}$

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 conserven todos los invariantes garantizados por los supertipos en algún contrato . ^[6] Esta definición de subtipificación 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 los valores de parámetros y valores de retorno. Las referencias de solo escritura (o sumideros ) son contravariantes, como los valores de 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.

Relación con la herencia

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

S no es un subtipo ni un tipo derivado de T
S es un subtipo pero no es un tipo derivado de T
S no es un subtipo sino un tipo derivado de T
S es a la vez un subtipo y un tipo derivado de T

El primer caso se ilustra mediante tipos independientes, como Booleany Float.

El segundo caso se puede ilustrar con 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, Int32se pueden considerar un subtipo de Int64ya que cualquier valor entero de 32 bits se puede convertir en un valor entero de 64 bits.

El tercer caso es una consecuencia de la subtipificación de funciones por 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 , observe también que el primer parámetro de m es this/self) y una clase derivada de tipo S de T . Por herencia, el tipo de m en S es S → S . ^{[ cita requerida ]} 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 requerida ]} , en otras palabras: S → S ≤: T → T . Por aplicación de abajo hacia arriba de la regla de subtipificación de funciones, esto significa: S ≤: T y T ≤: S , lo 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 .

La subtipificación 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]

Coerciones

En los sistemas de subtipificación coercitiva, 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 ), se proporciona una función de coerción coerce : S → T , y cualquier objeto s de tipo S se considera 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 un objeto de tipo u bajo la coerción compuesta ( coerce _{T → U} ∘ coerce _{S → T} ). La coerción de tipo de un tipo a sí mismo coerce _{T → T} es la función identidad id _T .

Las funciones de coerción para registros y subtipos de unión disjuntos pueden definirse por componentes; en el caso de registros de ancho extendido, la coerción de tipo simplemente descarta cualquier componente que no esté definido en el supertipo. La coerción de tipo para tipos de función puede darse por f' ( t ) = coerce _{S ₂ → T ₂} ( f ( coerce _{T ₁ → S ₁} ( 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 subtipo, se debe tener cuidado de garantizar que todas las coerciones de tipo sean coherentes. Por ejemplo, si un entero como 2 : int se puede convertir en un número de punto flotante (por ejemplo, 2.0 : float ), entonces no es admisible convertir 2.1 : float en 2 : int , porque la coerción compuesta coerce _{float → float} dada por coerce _{int → float} ∘ coerce _{float → int} sería entonces distinta de la coerción de identidad id _float .

Véase también

El Wikilibro Programación Ada tiene una página sobre el tema: Subtipos

Covarianza y contravarianza
El problema del círculo-elipse (por los peligros de subtipificar los tipos de variables sobre la misma base que los tipos de valores)
Programación basada en clases
Tipo superior
Tipo de refinamiento
Subtipificación del comportamiento

Notas

^ Copestake, Ann. Implementación de gramáticas de estructura de características tipificadas. Vol. 110. Stanford: publicaciones CSLI, 2002.
^ Cardelli, Luca. Una semántica de la herencia múltiple. En G. Kahn, D. MacQueen y G. Plotkin, editores, Semantics of Data Types, volumen 173 de Lecture Notes in Computer Science, páginas 51–67. Springer-Verlag, 1984. Versión completa en Information and Computation, 76(2/3):138–164, 1988.
^ por Cook, Hill y Canning 1990.
^ Pierce, cap. 15 notas
^ Benjamin C. Pierce, Tipos y lenguajes de programación , MIT Press, 2002, 15.1 "Subsumption", pág. 181-182
^ Barbara Liskov, Jeannette Wing, A behavioral notion of subtyping , ACM Transactions on Programming Languages and Systems, Volumen 16, Número 6 (noviembre de 1994), págs. 1811–1841. Una versión actualizada apareció como informe técnico de CMU: Liskov, Barbara ; Wing, Jeannette (julio de 1999). "Behavioral Subtyping Using Invariants and Constraints" ( PS ) . Consultado el 5 de octubre de 2006 .

Referencias

Libros de texto

Benjamin C. Pierce, Types and programming language (Tipos y lenguajes de programación ), MIT Press, 2002, ISBN 0-262-16209-1 , capítulo 15 (subtipificación de tipos de registros), 19.3 (tipos nominales y estructurales y subtipificación) y 23.2 (variedades de polimorfismo)
C. Szyperski, D. Gruntz, S. Murer, Component software: beyond object-oriented programming , 2.ª ed., Pearson Education, 2002, ISBN 0-201-74572-0 , págs. 93-95 (una presentación de alto nivel dirigida a los usuarios de lenguajes de programación)

Papeles

Cook, William R.; Hill, Walter; Canning, Peter S. (1990). La herencia no es subtipificación . Actas del 17.º Simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación (POPL). pp. 125–135. CiteSeerX 10.1.1.102.8635 . doi :10.1145/96709.96721. ISBN . 0-89791-343-4.

Reynolds, John C. Uso de la teoría de categorías para diseñar conversiones implícitas y operadores genéricos. En ND Jones, editor, Proceedings of the Aarhus Workshop on Semantics-Directed Compiler Generation, número 94 en Lecture Notes in Computer Science. Springer-Verlag, enero de 1980. También en Carl A. Gunter y John C. Mitchell, editores, Theoretical Aspects of Object-Oriented Programming: Types, Semantics, and Language Design (MIT Press, 1994).

Lectura adicional

John C. Reynolds , Teorías de lenguajes de programación , Cambridge University Press, 1998, ISBN 0-521-59414-6 , capítulo 16.
Martín Abadi , Luca Cardelli , Una teoría de los objetos , Springer, 1996, ISBN 0-387-94775-2 . En la sección 8.6 se contrasta la subtipificación de registros y objetos.