Hispanopedia Wiki
Articulo de referencia

Tipo de intersección

En la teoría de tipos , se puede asignar un tipo de intersección a valores que pueden ser asignados tanto al tipo σ {\displaystyle \sigma } y el tipo τ {\displaystyle \tau } . A...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría de tipos , se puede asignar un tipo de intersección a valores que pueden ser asignados tanto al tipoσ{\displaystyle \sigma }y el tipoτ{\displaystyle \tau }. A este valor se le puede asignar el tipo de intersección.σ∩τ{\displaystyle \sigma \cap \tau }en un sistema de tipos de intersección . [ 1 ] Generalmente, si los rangos de valores de dos tipos se superponen, entonces a un valor perteneciente a la intersección de los dos rangos se le puede asignar el tipo de intersección de estos dos tipos. Dicho valor se puede pasar de forma segura como argumento a funciones que esperan cualquiera de los dos tipos. Por ejemplo, en Java la clase Booleanimplementa las interfaces Serializabley Comparable. Por lo tanto, un objeto de tipo Booleanse puede pasar de forma segura a funciones que esperan un argumento de tipo Serializabley a funciones que esperan un argumento de tipo Comparable.

Los tipos de intersección son tipos de datos compuestos . Al igual que los tipos de producto , se utilizan para asignar varios tipos a un objeto. Sin embargo, los tipos de producto se asignan a tuplas , de modo que a cada elemento de la tupla se le asigna un componente de tipo de producto específico. En comparación, los objetos subyacentes de los tipos de intersección no son necesariamente compuestos. Una forma restringida de los tipos de intersección son los tipos de refinamiento .

Los tipos de intersección son útiles para describir funciones sobrecargadas . [ 2 ] Por ejemplo, si es el tipo de función que toma un número como argumento y devuelve un número, y es el tipo de función que toma una cadena como argumento y devuelve una cadena, entonces la intersección de estos dos tipos se puede usar para describir funciones (sobrecargadas) que hacen una u otra, según el tipo de entrada que se les dé.number=>numberstring=>string

Los lenguajes de programación contemporáneos, como Ceylon , Flow, Java , Scala , TypeScript y Whiley (véase la comparación de lenguajes con tipos de intersección ), utilizan tipos de intersección para combinar especificaciones de interfaz y expresar polimorfismo ad hoc . Complementando el polimorfismo paramétrico , los tipos de intersección pueden utilizarse para evitar la contaminación de la jerarquía de clases por aspectos transversales y reducir el código repetitivo , como se muestra en el ejemplo de TypeScript a continuación.

El estudio de la teoría de tipos de intersección se conoce como la disciplina de tipos de intersección . [ 3 ] Cabe destacar que la terminación de un programa puede caracterizarse con precisión utilizando tipos de intersección. [ 4 ] En consecuencia, la inferencia de tipos para tipos de intersección infinitos es indecidible , pero es decidible para todos los tipos de intersección de rango finito. [ 5 ]

Ejemplo de TypeScript

TypeScript admite tipos de intersección, [ 6 ] mejorando la expresividad del sistema de tipos y reduciendo el tamaño potencial de la jerarquía de clases, como se demuestra a continuación.

El siguiente código de programa define las clases Chicken, Cow, y RandomNumberGeneratorque cada una tiene un método produceque devuelve un objeto de tipo Egg, Milk, o number. Además, las funciones eatEggy drinkMilkrequieren argumentos de tipo Eggy Milk, respectivamente.

clase Huevo { privado tipo : "Huevo" ; }clase Leche { privado tipo : "Leche" ; }// "Produce" una interfaz de producto Producer < T > { produce () : T ; }// produce huevos class Chicken implements Producer < Egg > { produce () : Egg { return new Egg (); } }// produce leche class Cow implements Producer < Milk > { produce () : Milk { return new Milk (); } }// produce un número aleatorio class RandomNumberGenerator implements Producer < number > { produce () : number { return Math . random (); } }// requiere una función huevo eatEgg ( huevo : Huevo ) : cadena { return "Comí un huevo." ; }// requiere leche función drinkMilk ( leche : Leche ) : cadena { return "Tomé un poco de leche." ; }

El siguiente código de programa define la función polimórfica ad hocanimalToFood que invoca la función miembro producedel objeto dado animal. La función animalToFoodtiene dos anotaciones de tipo, a saber , y , conectadas a través del constructor de tipo de intersección . Específicamente, cuando se aplica a un argumento de tipo devuelve un objeto de tipo , y cuando se aplica a un argumento de tipo devuelve un objeto de tipo . Idealmente, no debería ser aplicable a ningún objeto que tenga (posiblemente por casualidad) un método .((_:Chicken)=>Egg)((_:Cow)=>Milk)&animalToFoodChickenEggCowMilkanimalToFoodproduce

// dado un pollo, produce un huevo; dado una vaca, produce leche const animalToFood : (( animal : Chicken ) => Egg ) & (( animal : Cow ) => Milk ) = ( animal : any ) => { return animal . produce (); };

Finalmente, el siguiente código de programa demuestra el uso seguro de tipos de las definiciones anteriores.

let pollo : Pollo = nuevo Pollo ();let vaca : Vaca = nueva Vaca ();let randomNumberGenerator : RandomNumberGenerator = new RandomNumberGenerator ();console.log ( chicken.produce ( )); // Huevo { }console.log ( vaca.produce ( )); // Leche { }console.log ( randomNumberGenerator.produce ( ) ) ; // 0.2626353555444987console.log ( animalToFood ( chicken )); // Huevo { }console.log ( animalToFood ( vaca )); // Leche { }// console.log(animalToFood(randomNumberGenerator)); // ERROR: El argumento de tipo 'RandomNumberGenerator' no es asignable al parámetro de tipo 'Cow'console.log ( eatEgg ( animalToFood ( chicken ) )); // Me comí un huevo.// console.log(eatEgg(animalToFood(cow))); // ERROR: El argumento de tipo 'Milk' no es asignable al parámetro de tipo 'Egg'console.log ( drinkMilk ( animalToFood ( cow ) )); // Bebí un poco de leche .// console.log(drinkMilk(animalToFood(chicken))); // ERROR: El argumento de tipo 'Egg' no es asignable al parámetro de tipo 'Milk'

El código del programa anterior tiene las siguientes propiedades:

  • Las líneas 1 a 3 crean objetos chicken, cow, y randomNumberGeneratorde su tipo respectivo.
  • Las líneas 5 a 7 imprimen para los objetos creados previamente los resultados respectivos (proporcionados como comentarios) al invocar produce.
  • La línea 9 (o 10) demuestra el uso seguro del método animalToFoodaplicado a chicken(o cow).
  • La línea 11, si no se comenta, resultaría en un error de tipo en tiempo de compilación. Aunque la implementación de animalToFoodpodría invocar el producemétodo de randomNumberGenerator, la anotación de tipo de animalToFoodlo prohíbe. Esto está de acuerdo con el significado previsto de animalToFood.
  • La línea 13 (o 15) demuestra que al aplicar animalToFooda chicken(o cow) se obtiene un objeto de tipo Egg(o Milk).
  • La línea 14 (o 16) demuestra que aplicar animalToFooda cow(o chicken) no produce un objeto de tipo Egg(o Milk). Por lo tanto, si se descomentara, la línea 14 (o 16) generaría un error de tipo en tiempo de compilación.

Comparación con la herencia

El ejemplo minimalista anterior se puede implementar mediante herencia , por ejemplo, derivando las clases Chickena Cowpartir de una clase base Animal. Sin embargo, en un entorno más amplio, esto podría resultar desventajoso. Introducir nuevas clases en una jerarquía de clases no siempre se justifica por cuestiones transversales , o incluso puede ser directamente imposible, por ejemplo, al usar una biblioteca externa. Es posible que el ejemplo anterior se amplíe con las siguientes clases:

  • una clase Horseque no tiene un producemétodo;
  • una clase Sheepque tiene un producemétodo que devuelve Wool;
  • una clase Pigque tiene un producemétodo, que se puede usar solo una vez, que devuelve Meat.

Esto podría requerir clases (o interfaces) adicionales que especifiquen si el método `produce` está disponible, si devuelve alimento y si puede usarse repetidamente. En general, esto podría complicar la jerarquía de clases.

Comparación con la tipificación dinámica (duck typing).

El ejemplo minimalista anterior ya muestra que el tipado dinámico es menos adecuado para realizar el escenario dado. Si bien la clase RandomNumberGeneratorcontiene un producemétodo, el objeto randomNumberGeneratorno debería ser un argumento válido para animalToFood. El ejemplo anterior se puede realizar usando tipado dinámico, por ejemplo, introduciendo un nuevo campo argumentForAnimalToFooda las clases Chickeny Cowseñalando que los objetos del tipo correspondiente son argumentos válidos para animalToFood. Sin embargo, esto no solo aumentaría el tamaño de las clases respectivas (especialmente con la introducción de más métodos similares a animalToFood), sino que también es un enfoque no local con respecto a animalToFood.

Comparación con la sobrecarga de funciones

El ejemplo anterior se puede implementar mediante la sobrecarga de funciones , por ejemplo, implementando dos métodos . En TypeScript, esta solución es casi idéntica al ejemplo proporcionado. Otros lenguajes de programación, como Java , requieren implementaciones distintas del método sobrecargado. Esto puede generar duplicación de código o código repetitivo .animalToFood(animal:Chicken):EgganimalToFood(animal:Cow):Milk

Comparación con el patrón de visitantes

El ejemplo anterior se puede realizar utilizando el patrón Visitor . Requeriría que cada clase de animal implementara un acceptmétodo que acepte un objeto que implemente la interfaz (añadiendo código repetitivoAnimalVisitor no local ). La función se realizaría como el método de una implementación de . Desafortunadamente, la conexión entre el tipo de entrada ( o ) y el tipo de resultado ( o ) sería difícil de representar.animalToFoodvisitAnimalVisitorChickenCowEggMilk

Comparación con el polimorfismo paramétrico

El polimorfismo paramétrico es conceptualmente equivalente a los tipos de intersección infinitos. [ 7 ]

Los tipos de intersección se han promovido como "composicionales" en contraste con el polimorfismo de let-bound de ML (una forma restringida de polimorfismo paramétrico) porque los tipos de intersección tienen tipados principales, mientras que el sistema de tipos de ML no los tiene (no confundir con los tipos principales, que ML sí posee). La falta de tipados principales en ML se traduce en la necesidad de evaluar algunas expresiones antes que otras en un programa ML; lo que esencialmente resulta en una dependencia de datos a nivel de inferencia de tipos en ML, en particular en letlas expresiones. [ 8 ] En consecuencia, los tipos de intersección se han propuesto como una forma de mejorar la compilación incremental [ 9 ] y/o el tipado gradual . [ 10 ]

Por otro lado, los tipos de intersección han sido criticados por no ser compositivos en otro sentido, a saber, que en un sistema hipotético que solo utiliza tipos de intersección pero no tiene polimorfismo paramétrico, los tipos inferidos pueden depender de las características locales de un módulo, lo que puede resultar en una mala composición con otros módulos a menos que la compilación completa del programa se realice a nivel de código fuente. Como ejemplo trivial, una función identidad expuesta a través de una interfaz pública, por ejemplo, exportada por un módulo, idealmente es paramétricamente polimórfica, de modo que puede utilizarse con tipos futuros que el autor (de esa función) aún desconoce. Sin embargo, en un sistema que solo tiene tipos de intersección, se inferiría que dicha función intersecta, en el mejor de los casos, sobre tipos existentes en el momento de su compilación. [ 11 ]

Limitaciones

Por un lado, los tipos de intersección permiten anotar localmente diferentes tipos en una función sin introducir nuevas clases (o interfaces) en la jerarquía de clases. Por otro lado, este enfoque requiere que se especifiquen explícitamente todos los tipos de argumentos y resultados posibles. Si el comportamiento de una función puede especificarse con precisión mediante una interfaz unificada, polimorfismo paramétrico o tipado dinámico , la verbosidad de los tipos de intersección resulta desfavorable. Por lo tanto, los tipos de intersección deben considerarse complementarios a los métodos de especificación existentes.

Tipo de intersección dependiente

Un tipo de intersección dependiente , denotado(incógnita:σ)∩τ{\displaystyle (x:\sigma )\cap \tau }, es un tipo dependiente en el que el tipoτ{\displaystyle \tau }puede depender de la variable del términoincógnita{\displaystyle x}. [ 12 ] En particular, si un términoMETRO{\displaystyle M}tiene el tipo de intersección dependiente(incógnita:σ)∩τ{\displaystyle (x:\sigma )\cap \tau }, entonces el términoMETRO{\displaystyle M}tiene ambos tiposσ{\displaystyle \sigma }y el tipoτ[incógnita:=METRO]{\displaystyle \tau [x:=M]}, dóndeτ[incógnita:=METRO]{\displaystyle \tau [x:=M]}es el tipo que resulta de reemplazar todas las ocurrencias del término variableincógnita{\displaystyle x}enτ{\displaystyle \tau }por el términoMETRO{\displaystyle M}.

Ejemplo de Scala

Scala admite declaraciones de tipo [ 13 ] como miembros de objetos. Esto permite que el tipo de un miembro de objeto dependa del valor de otro miembro, lo que se denomina tipo dependiente de ruta . [ 14 ] Por ejemplo, el siguiente texto de programa define un rasgo de Scala Witness, que puede utilizarse para implementar el patrón singleton . [ 15 ]

rasgo Testigo { tipo T valor : T { } }

El rasgo anterior Witnessdeclara el miembro T, al que se le puede asignar un tipo como su valor, y el miembro value, al que se le puede asignar un valor de tipo T. El siguiente texto del programa define un objeto booleanWitnesscomo instancia del rasgo anterior Witness. El objeto booleanWitnessdefine el tipo Tcomo Booleany el valor valuecomo true. Por ejemplo, la ejecución imprime en la consola.System.out.println(booleanWitness.value)true

objeto booleanWitness extiende Witness { tipo T = Boolean valor = verdadero }​

Dejar⟨incógnita:σ⟩{\displaystyle \langle {\textsf {x}}:\sigma \rangle }ser el tipo (específicamente, un tipo de registro ) de objetos que tienen el miembroincógnita{\displaystyle {\textsf {x}}}de tipoσ{\displaystyle \sigma }En el ejemplo anterior, al objeto booleanWitnessse le puede asignar el tipo de intersección dependiente .(incógnita:⟨T:Tipo⟩)∩⟨valor:incógnita.T⟩{\displaystyle (x:\langle {\textsf {T}}:{\text{Tipo}}\rangle )\cap \langle {\textsf {valor}}:x.{\textsf {T}}\rangle }El razonamiento es el siguiente. El objeto booleanWitnesstiene el miembro Tal que se le asigna el tipo Booleancomo su valor. Dado que Booleanes un tipo, el objeto booleanWitnesstiene el tipo⟨T:Tipo⟩{\displaystyle \langle {\textsf {T}}:{\text{Tipo}}\rangle }. Además, el objeto booleanWitnesstiene el miembro valueal que se le asigna el valor truede tipo Boolean. Dado que el valor de es , el objeto tiene el tipobooleanWitness.TBooleanbooleanWitness⟨valor:testigo booleano.T⟩{\displaystyle \langle {\textsf {valor}}:{\textsf {booleanWitness.T}}\rangle }En general, el objeto booleanWitnesstiene el tipo de intersección .⟨T:Tipo⟩∩⟨valor:testigo booleano.T⟩{\displaystyle \langle {\textsf {T}}:{\text{Tipo}}\rangle \cap \langle {\textsf {valor}}:{\textsf {booleanWitness.T}}\rangle }Por lo tanto, al presentar la autorreferencia como dependencia, el objeto booleanWitnesstiene el tipo de intersección dependiente.(incógnita:⟨T:Tipo⟩)∩⟨valor:incógnita.T⟩{\displaystyle (x:\langle {\textsf {T}}:{\text{Tipo}}\rangle )\cap \langle {\textsf {valor}}:x.{\textsf {T}}\rangle }.

Alternativamente, el ejemplo minimalista anterior puede describirse utilizando tipos de registro dependientes . [ 16 ] En comparación con los tipos de intersección dependientes, los tipos de registro dependientes constituyen un concepto de teoría de tipos estrictamente más especializado. [ 12 ]

Intersección de una familia de tipos

Una intersección de una familia de tipos , denotada⋂incógnita:στ{\textstyle \bigcap _{x:\sigma }\tau }, es un tipo dependiente en el que el tipoτ{\displaystyle \tau }puede depender de la variable del términoincógnita{\displaystyle x}. En particular, si un términoMETRO{\displaystyle M}tiene el tipo⋂incógnita:στ{\textstyle \bigcap _{x:\sigma }\tau }, luego para cada términonorte{\displaystyle N}de tipoσ{\displaystyle \sigma }, el términoMETRO{\displaystyle M}tiene el tipoτ[incógnita:=norte]{\displaystyle \tau [x:=N]}. Esta noción también se denomina tipo Pi implícito , [ 17 ] observando que el argumentonorte{\displaystyle N}no se mantiene a nivel de trimestre.

Comparación de lenguas con tipos de intersección

Referencias

  1. ↑ Barendregt, Henk; Coppo, Mario; Dezani-Ciancaglini, Mariangiola (1983). "Un modelo lambda de filtro y la completitud de la asignación de tipos". Journal of Symbolic Logic . 48 (4): 931– 940. doi : 10.2307/2273659 . JSTOR 2273659 . S2CID 45660117 .  
  2. ↑ Palsberg, Jens (2012). "La sobrecarga es NP-completa". Lógica y semántica de programas . Notas de clase en informática. Vol. 7230. pp. 204–218 . doi : 10.1007/978-3-642-29485-3_13 . ISBN   978-3-642-29484-6.
  3. ↑ Henk Barendregt; Wil Dekkers; Richard Statman (20 de junio de 2013). Cálculo Lambda con tipos . Prensa de la Universidad de Cambridge. págs.1– . ISBN  978-0-521-76614-2.
  4. ↑ Ghilezan, Silvia (1996). "Normalización fuerte y tipabilidad con tipos de intersección" . Notre Dame Journal of Formal Logic . 37 (1): 44– 52. doi : 10.1305/ndjfl/1040067315 .
  5. ↑ Kfoury, AJ; Wells, JB (enero de 2004). "Principalidad e inferencia de tipos para tipos de intersección usando variables de expansión". Theoretical Computer Science . 311 ( 1–3 ): 1–70 . doi : 10.1016/j.tcs.2003.10.032 .
  6. 1 2 "Tipos de intersección en TypeScript" . Consultado el 1 de agosto de 2019 .
  7. ↑ Giuseppe Castagna, Programming with Union, Intersection, and Negation Types, https://arxiv.org/pdf/2111.03354 p. 7 También capítulo 12 en "The French School of Programming", Springer 2024, ISBN 978-3-031-34517-3
  8. ↑ Wells, JB (2003). "La esencia de los tipados principales". ICALP '02: Actas del 29.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación . págs. 913–925 . 
  9. ↑ Damiani, Ferruccio. "Tipos de intersección de rango 2 para módulos". PPDP '03: Actas de la 5.ª conferencia internacional ACM SIGPLAN sobre principios y práctica de la programación declarativa .
  10. ↑ Castagna, Giuseppe; Lanvin, Victor. "Tipificación gradual con tipos de unión e intersección". ICFP 2017 .
  11. ↑ Giuseppe Castagna, Mickaël Laurent, Kim Nguyễn, Inferencia de tipos polimórficos para lenguajes dinámicos, Actas de la ACM sobre lenguajes de programación (POPL) 2024, pág. 40:6
  12. 1 2 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 Ciencias de la Computación . LICS 2003. IEEE Computer Society. pp. 86– 95. CiteSeerX 10.1.1.89.4223 . doi : 10.1109/LICS.2003.1210048 .  
  13. ↑ "Declaraciones de tipo en Scala" . Consultado el 15 de agosto de 2019 .
  14. ↑ Amin, Nada; Grütter, Samuel; Odersky, Martin; Rompf, Tiark; Stucki, Sandro (2016). «La esencia de los tipos de objetos dependientes». Una lista de éxitos que pueden cambiar el mundo (PDF) . Lecture Notes in Computer Science. Vol. 9600. Springer. pp. 249–272 . doi : 10.1007/978-3-319-30936-1_14 . ISBN   978-3-319-30935-4.
  15. ↑ "Singletons en la biblioteca shapeless de Scala" . GitHub . Consultado el 15 de agosto de 2019 .
  16. ↑ Pollack, Robert (2000). "Registros con tipos dependientes para representar la estructura matemática". Demostración de teoremas en lógicas de orden superior, 13.ª Conferencia Internacional . TPHOLs 2000. Springer. pp. 462–479 . doi : 10.1007/3-540-44659-1_29 . 
  17. ↑ Stump, Aaron (2018). "De la realizabilidad a la inducción mediante la intersección dependiente" . Annals of Pure and Applied Logic . 169 (7): 637– 655. doi : 10.1016/j.apal.2018.03.002 .
  18. ↑ "Guía de C#" . Consultado el 8 de agosto de 2019 .
  19. ↑ "Discusión: Tipos de unión e intersección en C#" . GitHub . Consultado el 8 de agosto de 2019 .
  20. ↑ "Eclipse Ceylon™" . 19 de julio de 2017. Consultado el 16 de agosto de 2023 .
  21. ↑ "Tipos de intersecciones en Ceilán" . 19 de julio de 2017. Consultado el 8 de agosto de 2019 .
  22. ↑ "Fundamentos del software F#" . Consultado el 8 de agosto de 2019 .
  23. ↑ "Añadir tipos de intersección a F Sharp" . GitHub . Consultado el 8 de agosto de 2019 .
  24. ↑ "Flow: Un verificador de tipos estático para JavaScript" . Archivado del original el 8 de abril de 2022. Consultado el 8 de agosto de 2019 .
  25. ↑ "Sintaxis de tipo de intersección en Flow" . Consultado el 8 de agosto de 2019 .
  26. ↑ Reynolds, JC (1988). Diseño preliminar del lenguaje de programación Forsythe.
  27. ↑ "Software Java" . Consultado el 8 de agosto de 2019 .
  28. ↑ "IntersectionType (Java SE 12 y JDK 12)" . Consultado el 1 de agosto de 2019 .
  29. ↑ "php.net" .
  30. ↑ "PHP.Watch - PHP 8.1: Tipos de intersección" .
  31. ↑ "El lenguaje de programación Scala" . Consultado el 8 de agosto de 2019 .
  32. ↑ "Tipos compuestos en Scala" . Consultado el 1 de agosto de 2019 .
  33. ↑ "Tipos de intersección en Dotty" . Consultado el 1 de agosto de 2019 .
  34. ↑ "TypeScript - JavaScript escalable" . Consultado el 1 de agosto de 2019 .
  35. ↑ "Whiley: un lenguaje de programación de código abierto con verificación estática extendida" . Consultado el 1 de agosto de 2019 .
  36. ↑ "Especificación del lenguaje Whiley" (PDF) . Archivado del original (PDF) el 16 de enero de 2020. Consultado el 1 de agosto de 2019 .
Lecturas relacionadas
6 articulos
Type theoryIn mathematics and theoretical computer science , a type theory is the formal presentation of a specific type system . [a] Type theory is the acade...Java (lenguaje de programación)Java (lenguaje de programación)Java es un lenguaje de programación de alto nivel , basado en clases y orientado a objetos que está diseñado para tener la menor cantidad posible d...Tipo de datos compuestoEn informática , un tipo de datos compuesto es un tipo de datos que consta de tipos de datos escalares del lenguaje de programación y otros tipos c...Tipo de productoTipo de productoEn los lenguajes de programación y la teoría de tipos , un producto de tipos es otro tipo compuesto en una estructura. Los "operandos" del producto...{\displaystyle (a_{1},a_{2},\ldots ,a_{n})=(b_{1},b_{2},\ldots ,b_{n})}TuplaEn matemáticas , una tupla es una secuencia finita o lista ordenada de números o, de forma más general, objetos matemáticos , que se denominan elem...{\displaystyle f:\mathbb {N} \rightarrow \{n\in \mathbb {N} \,|\,n>5\}}Refinement typeIn type theory, a refinement type[1][2][3] is a type endowed with a predicate which is assumed to hold for any element of the refined type. Refinem...