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 asigne un tipo "genérico", utilizando variables en lugar de tipos reales, y luego instanciado con tipos particulares según sea necesario. ^[1]^{: 340} Las funciones y los tipos de datos paramétricamente polimórficos 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 paramétricamente polimórficas son uniformes : se comportan de manera idéntica independientemente del tipo en el que se instancian. ^[1]^{: 340}^[2]^{: 37} Por el contrario, a las definiciones polimórficas ad hoc se les da una definición distinta para cada tipo. Por lo tanto, el polimorfismo ad hoc generalmente solo puede admitir un número limitado de tales tipos distintos, ya que se debe proporcionar una implementación separada para cada tipo.

Definición básica

Es posible escribir funciones que no dependan de los tipos de sus argumentos. Por ejemplo, la función identidad simplemente devuelve su argumento sin modificar. Esto da lugar naturalmente a una familia de tipos potenciales, como , , , etc. El polimorfismo paramétrico permite obtener un tipo único y más general introduciendo una variable de tipo cuantificada universalmente : ${\mathsf {id}}(x)=x$ ${\mathsf {Int}}\to {\mathsf {Int}}$ ${\mathsf {Bool}}\to {\mathsf {Bool}}$ ${\mathsf {Cadena}}\to {\mathsf {Cadena}}$ ${\mathsf {id}}$

{\mathsf {id}}:\paratodos \alpha .\alpha \a \alpha

La definición polimórfica puede entonces instanciarse sustituyendo cualquier tipo concreto por , obteniéndose así la familia completa de tipos potenciales. ^[3] ${\estilo de visualización \alpha}$

La función identidad es un ejemplo particularmente extremo, pero muchas otras funciones también se benefician del polimorfismo paramétrico. Por ejemplo, una función que concatena dos listas no inspecciona los elementos de la lista, solo la estructura de la lista en sí. Por lo tanto, se puede dar una familia similar de tipos, como , , etc., donde denota una lista de elementos del tipo . Por lo tanto, el tipo más general es ${\mathsf {añadir}}$ ${\mathsf {añadir}}$ $[{\mathsf {Int}}]\times [{\mathsf {Int}}]\to [{\mathsf {Int}}]$ $[{\mathsf {Bool}}]\times [{\mathsf {Bool}}]\to [{\mathsf {Bool}}]$ ${\estilo de visualización [T]}$ ${\estilo de visualización T}$

{\mathsf {agregar}}:\para todos \alpha .[\alpha ]\veces [\alpha ]\a [\alpha ]

que puede instanciarse en cualquier tipo de la familia.

Se dice que las funciones paramétricamente polimórficas como y están parametrizadas sobre un tipo arbitrario . ^[4] Tanto y están parametrizadas sobre un único tipo, pero las funciones pueden estar parametrizadas sobre una cantidad arbitraria de tipos. Por ejemplo, a las funciones y que devuelven el primer y el segundo elemento de un par , respectivamente, se les pueden asignar los siguientes tipos: ${\mathsf {id}}$ ${\mathsf {añadir}}$ ${\estilo de visualización \alpha}$ ${\mathsf {id}}$ ${\mathsf {añadir}}$ ${\mathsf {fst}}$ ${\mathsf {snd}}$

{\begin{aligned}{\mathsf {fst}}&:\para todos \alpha .\para todos \beta .\alpha \veces \beta \a \alpha \\{\mathsf {snd}}&:\para todos \alpha .\para todos \beta .\alpha \veces \beta \a \beta \end{aligned}}

En la expresión , se instancia a y se instancia a en la llamada a , por lo que el tipo de la expresión general es . ${\mathsf {fst}}((3,{\mathsf {verdadero}}))$ ${\estilo de visualización \alpha}$ ${\mathsf {Int}}$ ${\estilo de visualización \beta}$ ${\mathsf {Booleano}}$ ${\mathsf {fst}}$ ${\mathsf {Int}}$

La sintaxis utilizada para introducir el polimorfismo paramétrico varía significativamente entre lenguajes de programación. Por ejemplo, en algunos lenguajes de programación, como Haskell , el cuantificador está implícito y puede omitirse. ^{[5] Otros lenguajes requieren que los tipos se instancian explícitamente en algunos o todos}los sitios de llamada de una función paramétricamente polimórfica . $\paratodos \alfa$

Historia

El polimorfismo paramétrico se introdujo por primera vez en los lenguajes de programación en ML en 1975. ^[6] Hoy en día 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 del polimorfismo de tipo son superficialmente similares al polimorfismo paramétrico, aunque también introducen aspectos ad hoc. Un ejemplo es la especialización de plantillas de C++ .

Predicatividad, impredicatividad y polimorfismo de rango superior

Polimorfismo de rango 1 (predicativo)

En un sistema de tipos predicativo (también conocido como sistema polimórfico prenex ), 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 se pueden escribir de forma que todos los cuantificadores se ubiquen en la posición más externa (prenex). Por ejemplo, considere la función descrita anteriormente, que tiene el siguiente tipo: ${\mathsf {añadir}}$

{\mathsf {agregar}}:\para todos \alpha .[\alpha ]\veces [\alpha ]\a [\alpha ]

Para aplicar esta función a un par de listas, se debe sustituir un tipo concreto por la variable de modo que el tipo de función resultante sea coherente con los tipos de los argumentos. En un sistema impredicativo , puede ser cualquier tipo, incluido un tipo que sea polimórfico en sí mismo; por lo tanto, se puede aplicar a pares de listas con elementos de cualquier tipo, incluso a listas de funciones polimórficas como ella misma. El polimorfismo en el lenguaje ML es predicativo. ^[^{cita requerida}^] 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 siempre sea posible. ${\estilo de visualización T}$ ${\estilo de visualización \alpha}$ ${\estilo de visualización T}$ ${\mathsf {añadir}}$ ${\mathsf {añadir}}$

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 polimorfismo impredicativo, la inferencia de tipos del sistema es incompleta a menos que el programador proporcione algunas anotaciones de tipos explícitas.

Polimorfismo de rango superior

Algunos sistemas de tipos admiten un constructor de tipo de función impredicativo aunque otros constructores de tipos sigan siendo predicativos. Por ejemplo, el tipo está permitido en un sistema que admite polimorfismo de rango superior, aunque puede que no lo esté. ^[7] $(\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T$ $[\forall \alpha .\alpha \rightarrow \alpha ]$

Se dice que un tipo es de rango k (para algún entero fijo k ) si ninguna ruta desde su raíz a un 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 admita polimorfismo de rango 2 permitiría pero no . Se dice que un sistema de tipos que admite tipos de rango arbitrario es "polimórfico de rango n ". $\paratodos$ $(\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T$ $((\forall \alpha .\alpha \rightarrow \alpha )\rightarrow T)\rightarrow T$

La inferencia de tipos para el polimorfismo de rango 2 es decidible, pero para el rango 3 y superior, no lo es. ^[8]^[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 de 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 la impredicatividad completa es el Sistema F , que permite la instanciación en cualquier tipo, incluido él mismo. $\forall \alpha .\alpha \to \alpha$

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

Polimorfismo paramétrico acotado

En 1985, Luca Cardelli y Peter Wegner reconocieron las ventajas de permitir límites en los parámetros de tipo. ^[9] Muchas operaciones requieren algún conocimiento de los tipos de datos, pero de lo contrario pueden funcionar paramétricamente. Por ejemplo, para verificar 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 para 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 al requerir que los tipos pertenezcan a una clase de tipo ; por lo tanto, la misma función tiene el tipo en Haskell. En la mayoría de los lenguajes de programación orientados a objetos que admiten el polimorfismo paramétrico, los parámetros se pueden restringir para que sean subtipos de un tipo dado (consulte los artículos Polimorfismo de subtipo y Programación genérica ). ${\textstyle \mathrm {Eq} \,\alpha \,\Rightarrow \alpha \,\rightarrow \left[\alpha \right]\rightarrow \mathrm {Bool} }$

Véase también

Notas

^ abcdef Benjamin C. Pierce (2002). Tipos y lenguajes de programación. MIT Press. ISBN 978-0-262-16209-8.
^ Strachey, Christopher (1967), Conceptos fundamentales en lenguajes de programación (apuntes de clase), Copenhague: Escuela internacional de verano en programación informática. Republicado en: Strachey, Christopher (1 de abril de 2000). "Conceptos fundamentales en lenguajes de programación". Computación simbólica y de orden superior . 13 (1): 11–49. doi :10.1023/A:1010000313106. ISSN 1573-0557. S2CID 14124601.
^ Yorgey, Brent. «Más polimorfismo y clases de tipos». www.seas.upenn.edu . Consultado el 1 de octubre de 2022 .
^ Wu, Brandon. "Polimorfismo paramétrico - Ayuda de SML". smlhelp.github.io . Consultado el 1 de octubre de 2022 .
^ "Haskell 2010 Language Report § 4.1.2 Syntax of Types" (Informe del lenguaje Haskell 2010 § 4.1.2 Sintaxis de tipos). 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 supone que todas las variables de tipo en una expresión de tipo Haskell están cuantificadas universalmente; no existe una sintaxis explícita para la cuantificación universal.
^ Milner, R. , Morris, L., Newey, M. "Una lógica para funciones computables con tipos reflexivos y polimórficos", Proc. Conferencia sobre prueba y mejora de programas , Arc-et-Senans (1975)
^ Kwang Yul Seo. "Blog de Haskell de Kwang: polimorfismo de alto rango". kseo.github.io . Consultado el 30 de septiembre de 2022 .
^ Kfoury, AJ; Wells, JB (1 de enero de 1999). "Principio 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 .
^ 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). "Une Extension de l'Interpretation 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 , 19 , París: 408–425, doi :10.1007/3-540-06859-7_148, ISBN 978-3-540-06859-4.
Milner, Robin (1978). "Una teoría del polimorfismo de tipos en programación" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 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.