Polimorfismo de classificação mais alta sem aplicação explícita ou subtipagem?

7

Então, eu estou familiarizado com duas estratégias principais de ter polimorfismo de classificação mais alta em um idioma:

  • Polimorfismo no estilo System-F, em que as funções são explicitamente digitadas e a instanciação ocorre explicitamente no tipo de aplicativo. Esses sistemas podem ser impredicativos.
  • Polimorfismo baseado em subtipagem, em que um tipo polimórfico é um subtipo de todas as suas instanciações. Para ter uma subtipo decidível, o polimorfismo deve ser predicativo. Este documento fornece um exemplo desse sistema.

No entanto, algumas linguagens, como Haskell, têm polimorfismo impredicativo de classificação mais alta sem aplicativos explícitos.

Como isso é possível? Como a verificação de tipo "sabe" quando instanciar um tipo sem uma instanciação ou conversão explícita e sem uma noção de subtipagem?

Ou, tipechecking é mesmo decidível em tal sistema? É um caso em que linguagem como Haskell implementa algo indecidível que funciona para os casos de uso da maioria das pessoas.

EDITAR:

Para ser claro, estou interessado nos usos , não nas definições, dos valores digitados polimorficamente.

Por exemplo, suponha que tenhamos:

f : forall a . a -> a
g : (forall a . a -> a) -> Int
val = (g f, f True, f 'a')

Como podemos saber que precisamos instanciar fquando ela é aplicada, mas não quando é apresentada como argumento?

Ou, para nos separar dos tipos de função:

f : forall a . a
g : (forall a . a) -> Int
val = (g f, f && True, f + 0)

Aqui, não podemos sequer distinguir o uso de faplicá-lo versus passá-lo: ele é instanciado quando passado como argumento para &&e +, mas não g.

Como um sistema teórico pode distinguir esses dois casos sem uma regra mágica de "você pode converter qualquer tipo polimórfico em sua instância"? Ou com uma regra como essa, podemos saber quando aplicá-la, para manter a decisão?

programming-languages type-theory functional-programming type-checking polymorphisms jmite
fonte
Haskell nunca inferirá um polipo para uma variável de tipo, a menos que seja explicitamente fornecido pelo usuário. Por exemplo, \f -> (f True, f 'a')não vai tipo de verificação, mesmo se ele pode ser atribuído ao tipo(forall t. t->t) -> (Bool, Char)
chi
@chi Estou interessado nos usos , não nas definições, dos valores polimórficos, veja minha edição como um exemplo do que quero dizer. Desculpe se isso não estava claro no começo.
jmite
Deve haver algum artigo de Simon Peyton-Jones que explique o algoritmo de inferência (embora não possa apontar qual). Mas, provavelmente, o mecanismo de inferência pode ver que gespera um tipo e evita a instanciação de f.
Chi
@chi provavelmente microsoft.com/en-us/research/publication/… e microsoft.com/en-us/research/publication/…
phadej

Respostas:

7

A introdução do artigo de Dunfield e Krishnaswami refere-se à inferência prática de tipo para tipos de classificação arbitrária

Como pode ser visto, ele se adapta bem a sistemas do tipo avançado; além disso, é fácil de implementar e gera mensagens de erro de qualidade relativamente alta (Peyton Jones et al. 2007)

Na abordagem System F-ish, também há uma relação de "subtipagem". Consulte a seção 3.3 Subsunção.

Eu também enfatizaria que Haskell não tem tipos impredicativos (ou inferência para eles). Consulte: https://mail.haskell.org/pipermail/ghc-devs/2016-September/012940.html para obter indicadores.

  • Você pode escrever um polytype em um argumento de tipo visível; por exemplo. f @ (todos a. a-> a)

  • Você pode escrever um polytype como argumento de um tipo em uma assinatura, por exemplo, f :: [forall a. a-> a] -> Int

    E isso é tudo. Uma variável de unificação AINDA NÃO PODE ser unificada com um polipo. A única maneira de chamar uma função polimórfica em um polytype é usar o Visible Type Application.

Em resumo, se você chamar uma função em um polipo, deverá usar o VTA. Simples, fácil, previsível; e sem dúvida irritante. Mas possível.

Ou seja id id, sempre será elaborado como

forall a. id @(a -> a) (id @a)

não

id @(forall a. a -> a) id

No entanto, você pode escrever o último explicitamente, se ativar ImpredicativeTypes.

phadej
fonte
3

Para verificar a aplicação de uma função como g : (forall a. a -> a) -> Inta f, precisamos verificar isso f : forall a. a -> a.

Em vez de combinar quantificadores (que seriam bastante frágeis), introduzimos uma variável nova e rígida (ou seja, não unificável), digamos a1, e precisamos verificar isso f : a1 -> a1, e agora podemos continuar como de costume, instanciando fem a1(módulo adicional verificações para garantir que a1não escapa ao seu escopo).

O algoritmo real é detalhado no artigo phadej vinculado.

Ou, tipechecking é mesmo decidível em tal sistema? É um caso em que linguagem como Haskell implementa algo indecidível que funciona para os casos de uso da maioria das pessoas.

O problema geral da inferência de tipo na presença de polimorfismo de classificação mais alta permanece indecidível. No entanto, com anotações de tipo completo, torna-se um problema de verificação de tipo decidível (principalmente?) . O algoritmo do GHC deve, portanto, ser incompleto, mas tenta cobrir o máximo de terreno possível no meio dessas duas situações, com a ajuda de algumas anotações de tipo esparso.

Li-yao Xia
fonte