Hispanopedia Wiki
Articulo de referencia

Polimorfismo paramétrico

En los lenguajes de programación y la teoría de tipos , el polimorfismo paramétrico permite que a una sola pieza de código se le dé un tipo "genérico", usando variables en lugar...

Hispanopedia WikiContenido en espanolLectura gratuita

En los lenguajes de programación y la teoría de tipos , el polimorfismo paramétrico permite que a una sola pieza de código se le dé un tipo "genérico", usando variables en lugar de tipos reales, y luego se instancie con tipos particulares según sea necesario. [ 1 ] : 340 Las funciones y los tipos de datos polimórficos paramétricos a veces se denominan funciones genéricas y tipos de datos genéricos , respectivamente, y forman la base de la programación genérica .

El polimorfismo paramétrico puede contrastarse con el polimorfismo ad hoc . Las definiciones polimórficas paramétricas son uniformes : se comportan de forma idéntica independientemente del tipo en el que se instancien. [ 1 ] : 340 [ 2 ] : 37 En cambio, las definiciones polimórficas ad hoc reciben una definición distinta para cada tipo. Por lo tanto, el polimorfismo ad hoc generalmente solo puede admitir un número limitado de dichos tipos distintos, ya que se debe proporcionar una implementación separada para cada tipo.

El dispositivo teórico habitual para estudiar el polimorfismo paramétrico es el sistema F , que extiende el cálculo lambda simplemente tipado con cuantificación sobre tipos.

Definición básica

Es posible escribir funciones que no dependan de los tipos de sus argumentos. Por ejemplo, la función identidad.id(incógnita)=incógnita{\displaystyle {\mathsf {id}}(x)=x}simplemente devuelve su argumento sin modificar. Esto da lugar naturalmente a una familia de tipos potenciales, comoInortet→Inortet{\displaystyle {\mathsf {Int}}\to {\mathsf {Int}}},Bool→Bool{\displaystyle {\mathsf {Bool}}\to {\mathsf {Bool}}},Strinortegramo→Strinortegramo{\displaystyle {\mathsf {String}}\to {\mathsf {String}}}y así sucesivamente. El polimorfismo paramétrico permiteid{\displaystyle {\mathsf {id}}}se le asignará un único tipo , el más general, mediante la introducción de una variable de tipo cuantificada universalmente :

id:∀α.α→α{\displaystyle {\mathsf {id}}:\forall \alpha .\alpha \to \alpha }

La definición polimórfica puede entonces instanciarse sustituyendo cualquier tipo concreto porα{\displaystyle \alpha }, lo que da como resultado la familia completa de tipos potenciales. [ 3 ]

La función identidad es un ejemplo particularmente extremo, pero muchas otras funciones también se benefician del polimorfismo paramétrico. Por ejemplo, unaapagpagminorted{\displaystyle {\mathsf {append}}}La función que concatena dos listas no inspecciona los elementos de la lista, solo la estructura de la lista en sí. Por lo tanto,apagpagminorted{\displaystyle {\mathsf {append}}}se le puede dar una familia de tipos similar, como[Inortet]×[Inortet]→[Inortet]{\displaystyle [{\mathsf {Int}}]\times [{\mathsf {Int}}]\to [{\mathsf {Int}}]},[Bool]×[Bool]→[Bool]{\displaystyle [{\mathsf {Bool}}]\times [{\mathsf {Bool}}]\to [{\mathsf {Bool}}]}y así sucesivamente, donde[T]{\displaystyle [T]}denota una lista de elementos de tipoT{\displaystyle T}Por lo tanto, el tipo más general es

apagpagminorted:∀α.[α]×[α]→[α]{\displaystyle {\mathsf {append}}:\forall \alpha .[\alpha ]\times [\alpha ]\to [\alpha ]}

que se puede instanciar en cualquier tipo de la familia.

Funciones paramétricamente polimórficas comoid{\displaystyle {\mathsf {id}}}yapagpagminorted{\displaystyle {\mathsf {append}}}Se dice que están parametrizados sobre un tipo arbitrario.α{\displaystyle \alpha }. [ 4 ] Ambosid{\displaystyle {\mathsf {id}}}yapagpagminorted{\displaystyle {\mathsf {append}}}están parametrizados sobre un solo tipo, pero las funciones pueden estar parametrizadas sobre arbitrariamente muchos tipos. Por ejemplo, laFst{\displaystyle {\mathsf {fst}}}ysnorted{\displaystyle {\mathsf {snd}}}Las funciones que devuelven el primer y el segundo elemento de un par , respectivamente, pueden tener los siguientes tipos:

Fst:∀α.∀β.α×β→αsnorted:∀α.∀β.α×β→β{\displaystyle {\begin{aligned}{\mathsf {fst}}&:\forall \alpha .\forall \beta .\alpha \times \beta \to \alpha \\{\mathsf {snd}}&:\forall \alpha .\forall \beta .\alpha \times \beta \to \beta \end{aligned}}}

En la expresiónFst((3,trtúmi)){\displaystyle {\mathsf {fst}}((3,{\mathsf {true}}))},α{\displaystyle \alpha }se instancia paraInortet{\displaystyle {\mathsf {Int}}}yβ{\displaystyle \beta }se instancia paraBool{\displaystyle {\mathsf {Bool}}}en el llamado aFst{\displaystyle {\mathsf {fst}}}, por lo que el tipo de la expresión general esInortet{\displaystyle {\mathsf {Int}}}.

La sintaxis utilizada para introducir el polimorfismo paramétrico varía significativamente entre los lenguajes de programación. Por ejemplo, en algunos lenguajes de programación, como Haskell , la∀α{\displaystyle \forall \alpha }El cuantificador es implícito y puede omitirse. [ 5 ] Otros lenguajes requieren que los tipos se instancien explícitamente en los sitios de llamada de una función paramétricamente polimórfica , ya sea en todos los sitios o, alternativamente, al menos en los suficientes para permitir que la inferencia de tipos determine el resto.

Historia

El polimorfismo paramétrico se introdujo por primera vez en los lenguajes de programación en ML en 1975. [ 6 ] Hoy existe en Standard ML , OCaml , F# , Ada , Haskell , Mercury , Visual Prolog , Scala , Julia , Python , TypeScript , C++ y otros. Java , C# , Visual Basic .NET y Delphi han introducido "genéricos" para el polimorfismo paramétrico. Algunas implementaciones de polimorfismo de tipos son superficialmente similares al polimorfismo paramétrico, pero también introducen aspectos ad hoc. Un ejemplo es la especialización de plantillas de C++ .

En la década de 1980, Leivant introdujo una versión estratificada (es decir, predicativa) del sistema F de Girard y Reynolds . El enfoque de Leivant se basa en una noción de rango de los cuantificadores, que mide su profundidad de anidamiento dentro de los constructores de funciones . [ 7 ] El enfoque ML se limita al polimorfismo de rango 1 desde esta perspectiva. Haskell adoptó el polimorfismo paramétrico de rango superior en la década de 1990. Por ejemplo, el polimorfismo paramétrico de rango 2 se utiliza en Haskell para definir la runSTmónada , que simula eficazmente un sistema de tipos y efectos , [ 8 ] con "regiones aisladas de programación imperativa". A nivel de tipos, el aislamiento de estado proviene esencialmente de la cuantificación más profunda de rango 2 sobre el estado en runST. (Esto no es suficiente para describir formalmente la semántica en tiempo de ejecución de runST. Para esto último, se necesitan algunos ingredientes adicionales como la lógica de separación . [ 9 ] )

Predicatividad, impredicatividad y polimorfismo de rango superior

Se dice que un tipo es de rango k (para algún entero fijo k ) si no existe un camino desde su raíz hasta un∀{\displaystyle \forall }El cuantificador pasa a la izquierda de k o más flechas, cuando el tipo se dibuja como un árbol. [ 1 ] : 359 Se dice que un sistema de tipos admite polimorfismo de rango k si admite tipos con rango menor o igual a k . Por ejemplo, un sistema de tipos que admite polimorfismo de rango 2 permitiría(∀α.α→α)→T{\displaystyle (\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T}pero no((∀α.α→α)→T)→T{\displaystyle ((\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T)\rightarrow T}Se dice que un sistema de tipos que admite tipos de rango arbitrario es " polimórfico de rango n ".

(Esta noción de rango es diferente de cómo se define el rango de los cuantificadores en la lógica clásica, porque aquí mide la profundidad de anidamiento en relación con un conector no cuantificador , mientras que en la lógica clásica los conectores no cuantificadores no aumentan el rango de los cuantificadores anidados bajo ellos, pero otros cuantificadores sí lo hacen).

polimorfismo de rango 1 (predicativo)

En un sistema de tipos predicativo (también conocido como sistema polimórfico prenexo ), las variables de tipo no pueden instanciarse con tipos polimórficos. [ 1 ] : 359–360 Las teorías de tipos predicativos incluyen la teoría de tipos de Martin-Löf y Nuprl . Esto es muy similar a lo que se llama "estilo ML" o "polimorfismo Let" (técnicamente, el polimorfismo Let de ML tiene algunas otras restricciones sintácticas). Esta restricción hace que la distinción entre tipos polimórficos y no polimórficos sea muy importante; por lo tanto, en los sistemas predicativos, los tipos polimórficos a veces se denominan esquemas de tipos para distinguirlos de los tipos ordinarios (monomórficos), que a veces se denominan monotipos .

Una consecuencia de la predicatividad es que todos los tipos pueden escribirse de una forma que coloque todos los cuantificadores en la posición más externa (prenexa). Por ejemplo, considérese elapagpagminorted{\displaystyle {\mathsf {append}}}función descrita anteriormente, que tiene el siguiente tipo:

apagpagminorted:∀α.[α]×[α]→[α]{\displaystyle {\mathsf {append}}:\forall \alpha .[\alpha ]\times [\alpha ]\to [\alpha ]}

Para aplicar esta función a un par de listas, se requiere un tipo concreto.T{\displaystyle T}debe sustituirse por la variableα{\displaystyle \alpha }de tal manera que el tipo de función resultante sea consistente con los tipos de los argumentos. En un sistema impredicativo ,T{\displaystyle T}puede ser de cualquier tipo, incluyendo un tipo que sea en sí mismo polimórfico; por lo tantoapagpagminorted{\displaystyle {\mathsf {append}}}se puede aplicar a pares de listas con elementos de cualquier tipo, incluso a listas de funciones polimórficas comoapagpagminorted{\displaystyle {\mathsf {append}}}en sí mismo. El polimorfismo en el lenguaje ML es predicativo. [ 10 ] Esto se debe a que la predicatividad, junto con otras restricciones, hace que el sistema de tipos sea lo suficientemente simple como para que la inferencia de tipos completa sea siempre posible.

Como ejemplo práctico, OCaml (un descendiente o dialecto de ML ) realiza inferencia de tipos y admite polimorfismo impredicativo, pero en algunos casos, cuando se utiliza el polimorfismo impredicativo, la inferencia de tipos del sistema es incompleta a menos que el programador proporcione algunas anotaciones de tipo explícitas.

Polimorfismo de rango superior

Algunos sistemas de tipos admiten un constructor de tipo de función impredicativo aunque otros constructores de tipo sigan siendo predicativos. Por ejemplo, el tipo(∀α.α→α)→T{\displaystyle (\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T}está permitido en un sistema que admite polimorfismo de rango superior, aunque[∀α.α→α]{\displaystyle [\forall \alpha .\alpha \rightarrow \alpha ]}Puede que no lo sea. [ 11 ]

La inferencia de tipos para el polimorfismo de rango 2 es decidible, pero para el de rango 3 y superiores, no lo es. [ 12 ] [ 1 ] : 359

Polimorfismo impredicativo

El polimorfismo impredicativo (también llamado polimorfismo de primera clase ) es la forma más poderosa de polimorfismo paramétrico. [ 1 ] : 340 En lógica formal , se dice que una definición es impredicativa si es autorreferencial; en teoría de tipos, se refiere a la capacidad de un tipo para estar en el dominio de un cuantificador que contiene. Esto permite la instanciación de cualquier variable de tipo con cualquier tipo, incluidos los tipos polimórficos. Un ejemplo de un sistema que admite impredicatividad completa es el Sistema F , que permite instanciar∀α.α→α{\displaystyle \forall \alpha .\alpha \to \alpha }de cualquier tipo, incluido él mismo.

En teoría de tipos , los cálculos λ tipados impredicativos más estudiados se basan en los del cubo lambda , especialmente en el Sistema F.

Generalizaciones de la noción de rango

La noción de rango de Leivant puede generalizarse a símbolos distintos de los cuantificadores mediante una simple sustitución adecuada. Por ejemplo, puede aplicarse al (constructor de) tipos de intersección . Sin embargo, la jerarquía de tipos basada en rangos resultante puede tener propiedades diferentes. Por ejemplo, la inferencia de tipos para el sistema F de rango 3 o superior sigue siendo indecidible (como se detalla anteriormente); sin embargo, para los tipos de intersección, la inferencia de tipos es decidible para todos los rangos finitos. [ 13 ]

Polimorfismo paramétrico acotado

En 1985, Luca Cardelli y Peter Wegner reconocieron las ventajas de permitir límites en los parámetros de tipo. [ 14 ] Muchas operaciones requieren cierto conocimiento de los tipos de datos, pero por lo demás pueden funcionar paramétricamente. Por ejemplo, para comprobar si un elemento está incluido en una lista, necesitamos comparar los elementos para ver si son iguales. En Standard ML , los parámetros de tipo de la forma ''a están restringidos de modo que la operación de igualdad esté disponible, por lo que la función tendría el tipo ''a × ''a lista → bool y ''a solo puede ser un tipo con igualdad definida. En Haskell , la limitación se logra exigiendo que los tipos pertenezcan a una clase de tipo ; por lo tanto, la misma función tiene el tipomiqα⇒α→[α]→Bool{\textstyle \mathrm {Eq} \,\alpha \,\Rightarrow \alpha \,\rightarrow \left[\alpha \right]\rightarrow \mathrm {Bool} }en Haskell. En la mayoría de los lenguajes de programación orientados a objetos que admiten polimorfismo paramétrico, los parámetros pueden restringirse a ser subtipos de un tipo dado (véanse los artículos Polimorfismo de subtipos y Programación genérica ).

Véase también

Notas

  1. 1 2 3 4 5 6 Benjamin C. Pierce (2002). Tipos y lenguajes de programación . MIT Press. ISBN 978-0-262-16209-8.
  2. ↑ Strachey, Christopher (1967), Conceptos fundamentales en lenguajes de programación (apuntes de clase), Copenhague: Escuela Internacional de Verano de Programación Informática. Republicado en: Strachey, Christopher (1 de abril de 2000). "Conceptos fundamentales en lenguajes de programación" . Higher-Order and Symbolic Computation . 13 (1): 11– 49. doi : 10.1023/A:1010000313106 . ISSN 1573-0557 . S2CID 14124601 .  
  3. ↑ Yorgey, Brent. "Más polimorfismo y clases de tipos" . www.seas.upenn.edu . Consultado el 1 de octubre de 2022 .
  4. ↑ Wu, Brandon. "Polimorfismo paramétrico - Ayuda de SML" . smlhelp.github.io . Archivado del original el 1 de octubre de 2022. Consultado el 1 de octubre de 2022 .
  5. ↑ "Haskell 2010 Language Report § 4.1.2 Syntax of Types" . www.haskell.org . Consultado el 1 de octubre de 2022. Con una excepción (la de la variable de tipo distinguida en una declaración de clase (Sección 4.3.1)), se asume que todas las variables de tipo en una expresión de tipo de Haskell están cuantificadas universalmente; no existe una sintaxis explícita para la cuantificación universal.
  6. ↑ Milner, R. , Morris, L., Newey, M. "Una lógica para funciones computables con tipos reflexivos y polimórficos", Actas de la Conferencia sobre Demostración y Mejora de Programas , Arc-et-Senans (1975)
  7. ↑ D. Leivant, Inferencia de tipos polimórficos, en: Actas de la 10.ª Conferencia Anual del Simposio ACM sobre Principios de Lenguajes de Programación, 1983, págs. 88–98.
  8. ↑ E. Moggi y Amr Sabry. 2001. Encapsulación monádica de efectos: un enfoque revisado (versión extendida). J. Funct. Program. 11, 6 (noviembre de 2001), 591-627
  9. ↑ Amin Timany, Léo Stefanesco, Morten Krogh-Jespersen, Lars Birkedal, "Una relación lógica para la encapsulación monádica de estados: demostración de equivalencias contextuales en presencia de runST", POPL 2018
  10. ↑ Mitchell, JC; Harper, R. (13 de enero de 1988). "La esencia del aprendizaje automático" . Actas del 15.º simposio ACM SIGPLAN-SIGACT sobre principios de lenguajes de programación - POPL '88 . Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 28-46 . doi : 10.1145/73560.73563 . ISBN  978-0-89791-252-5.
  11. ↑ Kwang Yul Seo. "Blog de Haskell de Kwang: polimorfismo de rango superior" . kseo.github.io . Consultado el 30 de septiembre de 2022 .
  12. ↑ Kfoury, AJ; Wells, JB (1 de enero de 1999). «Principalidad e inferencia de tipos decidibles para tipos de intersección de rango finito». Actas del 26.º Simposio ACM SIGPLAN-SIGACT sobre Principios de Lenguajes de Programación . Association for Computing Machinery. págs. 161–174 . doi : 10.1145/292540.292556 . ISBN  1581130953. S2CID 14183560 . 
  13. ↑ 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 : 1–70 .
  14. ↑ Cardelli y Wegner 1985 .

Referencias

  • Hindley, J. Roger (1969), "El esquema de tipos principales de un objeto en lógica combinatoria", Transactions of the American Mathematical Society , 146 : 29–60 , doi : 10.2307/1995158 , JSTOR 1995158 , MR 0253905  .
  • Girard, Jean-Yves (1971). "Una extensión de la interpretación de Gödel à l'Analyse, et son Application à l'Élimination des Coupures dans l'Analyse et la Théorie des Types". Actas del Segundo Simposio de Lógica Escandinava . Estudios de lógica y fundamentos de las matemáticas (en francés). vol.  63. Ámsterdam. págs. 63– 92. doi : 10.1016/S0049-237X(08)70843-7 . ISBN  9780720422597.
  • Girard, Jean-Yves (1972), Interprétation fonctionnelle et elimination des coupures de l'arithmétique d'ordre supérieur (tesis doctoral) (en francés), Université Paris 7.
  • Reynolds, John C. (1974), "Hacia una teoría de la estructura de tipos" , Colloque Sur la Programmation , Lecture Notes in Computer Science , vol.  19, París, págs. 408–425 , doi : 10.1007/3-540-06859-7_148 , ISBN  978-3-540-06859-4{{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace ) .
  • Milner, Robin (1978). "Una teoría del polimorfismo de tipos en programación" (PDF) . Journal of Computer and System Sciences . 17 (3): 348– 375. doi : 10.1016/0022-0000(78)90014-4 . S2CID 388583 . 
  • 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 . ISSN 0360-0300 . S2CID 2921816 .   
  • Pierce, Benjamin C. (2002). Tipos y lenguajes de programación . MIT Press. ISBN 978-0-262-16209-8.