Polimorfismo y Genéricos

El polimorfismo permite que una sola pieza de código opere uniformemente sobre muchos tipos, siendo sus formas principales el polimorfismo paramétrico (genéricos), el polimorfismo ad hoc (sobrecarga y clases de tipos) y el polimorfismo de subtipos.

Definition

El polimorfismo es la propiedad por la cual una sola función, tipo u operación puede aplicarse a valores de más de un tipo; el polimorfismo paramétrico lo hace uniformemente a través de parámetros de tipo (genéricos), mientras que el polimorfismo ad hoc despacha a implementaciones específicas de tipo.

Scope

Este tema cubre los principales tipos de polimorfismo: el polimorfismo paramétrico realizado por genéricos y System F, el polimorfismo ad hoc a través de la sobrecarga y las clases de tipos, y el polimorfismo de inclusión (subtipo). Aborda la parametricidad y los sólidos principios de razonamiento que produce, y cómo se compilan y restringen las abstracciones genéricas.

Core questions

• ¿Cómo proporcionan los genéricos la reutilización sin sacrificar la seguridad de tipos?
• ¿Qué es la parametricidad y qué garantías ofrece de forma gratuita?
• ¿Cómo sistematizan las clases de tipos la sobrecarga ad hoc?
• ¿Cómo se compilan las definiciones genéricas y qué restricciones pueden limitar los parámetros de tipo?

Key theories

Parametricidad (teorema de abstracción)

El teorema de abstracción de Reynolds demuestra que las funciones paramétricamente polimórficas se comportan uniformemente en todos los tipos, una propiedad que restringe su posible comportamiento independientemente de la instanciación de tipo concreta.

Teoremas gratuitos

Wadler demostró que el tipo de una función paramétricamente polimórfica por sí solo implica teoremas gratuitos sobre su comportamiento, una consecuencia directa y práctica de la parametricidad.

Clases de tipos para una sobrecarga basada en principios

Wadler y Blott introdujeron las clases de tipos, dando al polimorfismo ad hoc una base coherente de teoría de tipos donde las operaciones sobrecargadas se resuelven pasando diccionarios implícitos de implementaciones de métodos.

Clinical relevance

Los genéricos y el polimorfismo son fundamentales para el diseño de bibliotecas reutilizables y marcos de colecciones en los lenguajes modernos. Las clases de tipos y sus análogos (rasgos, conceptos, protocolos) proporcionan una sobrecarga segura de tipos y basada en principios, mientras que la parametricidad apoya el razonamiento de corrección y las optimizaciones del compilador.

History

System F, que captura el polimorfismo paramétrico, fue descubierto independientemente por Girard y Reynolds a principios de la década de 1970. ML puso en práctica el polimorfismo con inferencia. La encuesta de Cardelli y Wegner de 1985 clasificó las formas de polimorfismo, Reynolds formalizó la parametricidad en 1983, y las clases de tipos de Wadler y Blott de 1989 dieron forma a la sobrecarga en Haskell e influyeron en los rasgos y conceptos en otros lugares.

Debates

Borrado versus genéricos reificados

Los implementadores de lenguajes debaten la compilación de genéricos mediante el borrado de tipos, que es simple pero pierde información de tipo en tiempo de ejecución, frente a la reificación de parámetros de tipo en tiempo de ejecución, que permite la introspección a un costo en complejidad y tamaño de código.

Key figures

• John Reynolds
• Jean-Yves Girard
• Philip Wadler
• Luca Cardelli
• Robin Milner

Seminal works

• reynolds1983
• wadler1989free
• wadler1989
• cardelli1985

Frequently asked questions

¿Cuál es la diferencia entre el polimorfismo paramétrico y el ad hoc?

El polimorfismo paramétrico aplica una implementación uniforme a todos los argumentos de tipo (como con los genéricos), mientras que el polimorfismo ad hoc selecciona una implementación específica de tipo, como con la sobrecarga o las clases de tipos.

¿Qué nos aporta la parametricidad?

La parametricidad garantiza que una función genérica trata todas las instancias de tipo de manera uniforme, lo que produce 'teoremas gratuitos' sobre su comportamiento, derivables únicamente de su firma de tipo.