Estoy trabajando en un lenguaje basado en expresiones de genealogía ML, por lo que naturalmente necesita inferencia de tipos> :)
Ahora, estoy tratando de extender una solución basada en restricciones al problema de inferir tipos, basada en una implementación simple en EOPL (Friedman y Wand), pero ellos eligen elegantemente los tipos de datos algebraicos.
Lo que tengo hasta ahora funciona sin problemas; si una expresión ees a + b, e : Int, a : Inty b : Int. Si ees un partido,
match n with
| 0 -> 1
| n' -> n' * fac(n - 1)`,
Puedo inferir con razón, que el t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1)y así sucesivamente ...
Pero no estoy muy seguro cuando se trata de tipos de datos algebraicos. Supongamos una función 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 el tipo de lista siga siendo polimórfico, Cons debe ser de tipo a * a list -> a list. Así, en el establecimiento de estas limitaciones, que obviamente tendrá que buscar estos tipos de mis constructores algebraicas - el problema que ahora tengo es la 'sensibilidad al contexto' de múltiples usos de constructores algebraicas - ¿Cómo expreso en mis ecuaciones de restricción que la ade cada caso debe ser igual?
Tengo problemas para encontrar una solución general a esto, y no puedo encontrar mucha literatura sobre esto. Cada vez que encuentro algo similar, un lenguaje basado en expresiones con inferencia de tipos basada en restricciones, se detienen poco menos que los tipos de datos algebraicos y el polimorfismo.
¡Cualquier aporte se agradecerá!
Respuestas:
Ver: Mini ML Específicamente la sección Inferencia de tipo.
Contiene código de muestra en F # para un analizador completo de un lenguaje funcional simple. Más importante aún, la sección de inferencia de tipo implementa el algoritmo Hindley-Milner, que es lo que se encuentra en la mayoría del sistema de inferencia de tipo. El autor también proporciona enlaces a otros dos documentos importantes para ayudar a comprender Hindley-Milner; uno es una especie de introducción de alto nivel y el otro es un documento que describe la implementación del algoritmo en código.
fuente