A inferência de Hindley-Milner poderia funcionar para o idioma Go?

22

Eu li que Hindley-Milner não funciona com sistemas de tipos que têm subclasses, e existem outros recursos do sistema de tipos que também não funcionam bem com ele. O Go atualmente possui apenas inferência de tipo muito limitada no :=operador. Mas Go não tem subclasses no sentido tradicional, apenas interfaces que se parecem muito com as classes de tipo de Haskell que funcionam bem com a inferência de Hindley-Milner.

Então, a inferência de Hindley-Milner poderia funcionar em princípio para Go da mesma maneira que para Haskell? Ou o Go tem outros recursos que o quebram? (Por outro lado, Haskell também possui alguns recursos que não funcionam com Hindly-Milner, se você os usar, precisará digitar manualmente essas partes do seu programa.)

JanKanis
fonte

Respostas:

35

A inferência do tipo Hindley-Milner é usada para sistemas do tipo Hindley-Milner, uma restrição dos sistemas do tipo System-F. A característica interessante dos sistemas do tipo HM é que eles têm polimorfismo paramétrico (também conhecido como genéricos). Esse é o maior recurso do sistema de tipos que a Golang se recusa a ter.

Com essa restrição frustrante, a inferência do tipo HM é impossível. Vamos dar uma olhada no código não digitado:

func f(a) {
  return a.method()
}

Qual é o tipo de f? Podemos perceber que adeve ter um método, para que pudéssemos usar uma interface anônimo: func f(a interface { method() ??? }) ???. No entanto, não temos idéia de qual é o tipo de retorno. Com variáveis ​​de tipo, poderíamos declarar o tipo como

func f[T](a interface{ method() T }) T

No entanto, o Go não possui variáveis ​​de tipo, portanto isso não funcionará. Embora as interfaces implícitas facilitem alguns aspectos da inferência de tipos, agora não temos como descobrir o tipo de retorno de uma chamada de função. O sistema HM requer que todas as funções sejam declaradas, e não implícitas, e cada nome pode ter apenas um único tipo (enquanto os métodos de Go podem ter tipos diferentes em diferentes interfaces).

Em vez disso, o Go requer que as funções sejam sempre totalmente declaradas, mas permite que as variáveis ​​usem inferência de tipo. Isso é possível porque o lado direito de uma atribuição variable := expressionjá possui um tipo conhecido naquele ponto do programa. Esse tipo de inferência de tipo é simples, correto e linear.

  • O tipo de uma variável é imediatamente conhecido no ponto da declaração, enquanto a inferência do HM deve verificar o tipo potencialmente todo o programa primeiro. Isso também tem um impacto perceptível na qualidade das mensagens de erro.
  • A abordagem de inferência de tipo da Go sempre seleciona o tipo mais específico para uma variável, em contraste com o HM, que escolhe o tipo mais geral. Isso funciona perfeitamente com a subtipagem, mesmo com as interfaces implícitas do Go.
amon
fonte
24
@bishop É "fundamentado" para valores infinitesimalmente pequenos de "razão".
hobbs
18
@bishop Tendo feito o trabalho do compilador em linguagens com genéricos, certamente posso concordar: é difícil de implementar sem complicar significativamente a implementação. Eu chegaria ao ponto de substituir "difícil" por "impossível". No entanto, esse não é o ponto; o ponto é, vale a pena a complicação extra? E a resposta, para quem trabalhou com e sem genéricos, é obviamente "sim, definitivamente!" Eu teria que concordar sinceramente com a afirmação de que se recusar a implementar genéricos porque "oh não, complexidade" é idiota.
Mason Wheeler
18
É também por isso que os desenvolvedores do Go fingem que todos os tipos de FP são ruins; Go tem funções de primeira classe com fechamento lexical, e com isso a capacidade de criar funções de ordem superior, mas é impossível colocá-los para qualquer bom uso, porque os tipos de tais funções básicas como map, filter, e reducesão todos inexprimível dentro Go muito limitado sistema de tipos.
precisa
9
@hobbs e ir poderia ser um realmente linguagem bom se que foram corrigidos, mas em vez disso as pessoas têm de escrever bibliotecas genérico geração, como gengenegonerics
cat
14
@cat É uma pena. No início, o Go parece ser uma ótima linguagem cheia de ótimas idéias, mas então você percebe que não tem herança e polimorfismo; portanto, você não pode fazer bem OOP e não possui genéricos; portanto, não pode fazer bem FP, e você ficou olhando fixamente para a tela perguntando "então como exatamente você deveria usar esse idioma?!?"
Mason Wheeler