Eu estou trabalhando em uma linguagem baseada em expressão da genealogia ML, então ela naturalmente precisa de inferência de tipo> :)
Agora, estou tentando estender uma solução baseada em restrições para o problema de inferir tipos, com base em uma implementação simples no EOPL (Friedman e Wand), mas eles datilografam elegantemente tipos de dados algébricos.
O que tenho até agora funciona sem problemas; se uma expressão eé a + b, e : Int, a : Inte b : Int. Se eé uma correspondência,
match n with
| 0 -> 1
| n' -> n' * fac(n - 1)`,
I pode justamente inferir que o t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1)e assim por diante ...
Mas não tenho muita certeza quando se trata de tipos de dados algébricos. Suponha uma função como filtro:
let filter pred list =
match list with
| Empty -> Empty
| Cons(e, ls') when pred e -> Cons (e, filter ls')
| Cons(_, ls') -> filter
Para que o tipo de lista permaneça polimórfico, os Contras precisam ser do tipo a * a list -> a list. Assim, ao estabelecer essas restrições, eu, obviamente, precisa olhar para cima estes tipos dos meus construtores algébricas - o problema agora tenho é o 'contexto-sensibilidade' dos usos múltiplos dos construtores algébricas - como posso expressar em meus equações de restrição que o ano cada caso precisa ser o mesmo?
Estou tendo problemas para encontrar uma solução geral para isso e não consigo encontrar muita literatura sobre isso. Sempre que encontro algo semelhante - linguagem baseada em expressões com inferência de tipo baseada em restrições - eles param um pouco antes dos tipos de dados algébricos e do polimorfismo.
Qualquer entrada é muito apreciada!
Respostas:
Consulte: Mini ML Especificamente na seção Inferência de tipo.
Ele contém código de exemplo em F # para um analisador completo de uma linguagem funcional simples. Mais importante, a seção Inferência de Tipo implementa o algoritmo Hindley-Milner, que é o encontrado na maioria dos sistemas de inferência de tipo. O autor também fornece links para dois outros documentos importantes para ajudar no entendimento da Hindley-Milner; um sendo uma espécie de introdução de alto nível e o outro um artigo que descreve a implementação do algoritmo no código.
fonte