Polimorfismo e Genéricos

O polimorfismo permite que uma única peça de código opere uniformemente sobre muitos tipos, com o polimorfismo paramétrico (genéricos), polimorfismo ad hoc (sobrecarga e classes de tipo) e polimorfismo de subtipo como suas principais formas.

Definition

Polimorfismo é a propriedade pela qual uma única função, tipo ou operação pode ser aplicada a valores de mais de um tipo; o polimorfismo paramétrico faz isso uniformemente via parâmetros de tipo (genéricos), enquanto o polimorfismo ad hoc despacha para implementações específicas de tipo.

Scope

Este tópico abrange os principais tipos de polimorfismo: polimorfismo paramétrico realizado por genéricos e System F, polimorfismo ad hoc via sobrecarga e classes de tipo, e polimorfismo de inclusão (subtipo). Aborda a parametricidade e os fortes princípios de raciocínio que ela proporciona, e como as abstrações genéricas são compiladas e restringidas.

Core questions

• Como os genéricos proporcionam reutilização sem sacrificar a segurança de tipo?
• O que é parametricidade e quais garantias ela oferece gratuitamente?
• Como as classes de tipo sistematizam a sobrecarga ad hoc?
• Como as definições genéricas são compiladas e quais restrições podem limitar os parâmetros de tipo?

Key theories

Parametricidade (teorema da abstração)

O teorema da abstração de Reynolds mostra que funções parametricamente polimórficas se comportam uniformemente em todos os tipos, uma propriedade que restringe seu possível comportamento independentemente da instanciação de tipo concreta.

Teoremas gratuitos

Wadler mostrou que o tipo de uma função parametricamente polimórfica por si só implica teoremas gratuitos sobre seu comportamento, uma consequência direta e prática da parametricidade.

Classes de tipo para sobrecarga principiada

Wadler e Blott introduziram as classes de tipo, dando ao polimorfismo ad hoc uma base teórica de tipos coerente onde as operações sobrecarregadas são resolvidas passando dicionários implícitos de implementações de métodos.

Clinical relevance

Genéricos e polimorfismo são centrais para o design de bibliotecas reutilizáveis e frameworks de coleção em linguagens modernas. Classes de tipo e seus análogos (traits, conceitos, protocolos) fornecem sobrecarga principiada e segura em termos de tipo, enquanto a parametricidade suporta o raciocínio de correção e otimizações do compilador.

History

O System F, que captura o polimorfismo paramétrico, foi descoberto independentemente por Girard e Reynolds no início dos anos 1970. ML trouxe o polimorfismo com inferência para a prática. O levantamento de Cardelli e Wegner de 1985 classificou as formas de polimorfismo, Reynolds formalizou a parametricidade em 1983, e as classes de tipo de Wadler e Blott de 1989 moldaram a sobrecarga em Haskell e influenciaram traits e conceitos em outros lugares.

Debates

Apagamento versus genéricos reificados

Os implementadores de linguagem debatem a compilação de genéricos por apagamento de tipo (type erasure), que é simples mas perde informações de tipo em tempo de execução, versus a reificação de parâmetros de tipo em tempo de execução, que permite a introspecção a um custo em complexidade e tamanho 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

Qual é a diferença entre polimorfismo paramétrico e ad hoc?

O polimorfismo paramétrico aplica uma implementação uniforme a todos os argumentos de tipo (como com genéricos), enquanto o polimorfismo ad hoc seleciona uma implementação específica de tipo, como com sobrecarga ou classes de tipo.

O que a parametricidade nos oferece?

A parametricidade garante que uma função genérica trata todas as instâncias de tipo uniformemente, o que produz 'teoremas gratuitos' sobre seu comportamento, deriváveis apenas de sua assinatura de tipo.