Descrever o tipo de inferência Damas-Milner de uma maneira que um estudante CS101 pode entender

Question

Hindley-Milner é um tipo de sistema que é a base dos sistemas de tipos de muitas linguagens de programação funcionais bem conhecidos. Damas-Milner é um algoritmo que infere (deduz?) Tipos em um sistema do tipo Hindley-Milner.

Wikipedia dá uma descrição do algoritmo que, como tanto quanto eu posso dizer, eleva-se a uma única palavra: "unificação" É que tudo o que há para isso? Se assim for, isso significa que a parte interessante é o próprio sistema do tipo não o sistema de inferência de tipos.

Se Damas-Milner é mais do que a unificação, gostaria uma descrição Damas-Milner, que inclui um exemplo simples e, de preferência, algum código.

Além disso, esse algoritmo é muitas vezes disse para fazer a inferência de tipos. É realmente um sistema de inferência? Eu pensei que estava apenas deduzir os tipos.

Perguntas relacionadas:

• O que é Hindley Miller?
• Tipo inferência problema unificação

Answer 1

Damas Milner é apenas um uso estruturado de unificação.

Quando se recurses em uma expressão lambda torna-se um novo nome variável. Quando, em um sub-prazo, encontrar essa variável utilizada de uma forma que seria necessário um determinado tipo, grava a unificação dessa variável e que tipo. Se alguma vez tenta unificar dois tipos que não fazem sentido, como dizer que uma variável individual é tanto um Int e uma função a partir de um -.> B, então ele grita com você para fazer algo ruim

Além disso, esse algoritmo é muitas vezes disse para fazer a inferência de tipos. É realmente um sistema de inferência? Eu pensei que estava apenas deduzir os tipos.

Deduzir os tipos é a inferência de tipos. Verificação para ver que tipo de anotações são válidos para um determinado termo é a verificação de tipo. Eles são problemas diferentes.

Se assim for, isso significa que a parte interessante é o próprio sistema do tipo não o sistema de inferência de tipos.

costuma dizer-se que sistemas do tipo estilo Hindley-Milner são equilibrados em uma cúspide. Se você adicionar muito mais funcionalidade torna-se impossível inferir os tipos. Então extensões do sistema tipo que você pode camada em cima de um sistema de tipo de estilo Hindley-Milner sem destruir suas propriedades de inferência são realmente as partes interessantes de linguagens funcionais modernos. Em alguns casos, nós misturamos tipo de inferência e verificação de tipo, por exemplo, em Haskell um monte de extensões modernas não pode ser inferida, mas pode ser verificado, para que eles exigem anotações de tipo de recursos avançados, como recursão polimórfico.

Answer 2

Wikipedia dá uma descrição do algoritmo que, tanto quanto eu posso dizer, eleva-se a uma única palavra: "unificação". É que tudo o que há para isso? Se assim for, isso significa que a parte interessante é o próprio sistema do tipo não o sistema de inferência de tipos.

IIRC, a parte interessante do tipo Damas-Milner inferência Algoritmo W é que ele infere os tipos mais geral possível.