Escriba inferencia al problema de la unificación

votos
2

Alguien tiene una idea de cómo el tipo de problema de inferencia

E > hd (cons 1 nil) : α0

con el entorno de tipeo

                E={
                   hd : list(α1 ) → α1 ,
                   cons : α2 → list(α2 ) → list(α2 ),
                   nil : list(α3 ),
                   1 : int
                }

se puede transferir en un problema de unificación?

¡Cualquier ayuda realmente sería apreciada!

Publicado el 09/12/2008 a las 14:58
fuente por usuario
En otros idiomas...                            


1 respuestas

votos
3

En primer lugar, cambie el nombre de las variables de tipo para que ninguna de las variables en su expresión colisione con las variables en el entorno de escritura. (En su ejemplo, esto ya está hecho ya que la expresión hace referencia a {a0}, y el entorno de escritura de texto hace referencia a {a1, a2, a3}.

En segundo lugar, utilizando nuevas variables de tipo, cree una variable de tipo para cada subexpresión dentro de su expresión, produciendo algo como:

nil : a4
1 : a5
cons : a6
(cons 1 nil) : a7
hd : a8
hd (cons 1 nil) : a0 // already had a type variable

En tercer lugar, genere un conjunto de ecuaciones entre las variables de tipo que deben contener. Puede hacer esto de abajo arriba, de arriba hacia abajo, o de otras maneras. Ver Heeren, Bastiaan. Mensajes de error de tipo de calidad superior. 2005. para obtener detalles detallados sobre por qué es posible que desee elegir de una manera u otra. Esto dará como resultado algo como:

a4 = list(a3) // = E(nil)
a5 = int // = E(1)
a6 = a2 -> list(a2) -> list(a2) // = E(cons)

// now it gets tricky, since we need to deal with application for the first time
a5 = a2 // first actual param of cons matches first formal param of cons
a4 = list(a2) // second actual param of cons matches type of second formal param of cons
a7 = list(a2) // result of (cons 1 nil) matches result type of cons with 2 params

a8 = list(a1) -> a1 // = E(hd)    

// now the application of hd
a7 = list(a1) // first actual param of hd matches type of first formal param of hd
a0 = a1 // result of hd (cons 1 nil) matches result type of hd with 1 param

Observe cuidadosamente que si la misma función se usara dos veces desde el entorno de tipo, necesitaríamos más variables de tipo nuevas (en el segundo paso, arriba) para unificar con, de modo que no hagamos accidentalmente todas las llamadas para usar el mismo tipo de contras. . No estoy seguro de cómo explicar esta parte más claramente, lo siento. Aquí estamos en el caso fácil, ya que hd y contras solo se usan una vez.

En cuarto lugar, unificar estas ecuaciones, lo que resulta en (si no me he equivocado) algo así como:

a4 = list(int)
a5 = int
a6 = int -> list(int) -> list(int)
a7 = list(int)
a8 = list(int) -> int
a0 = int

Regocíjate, ahora sabes el tipo de cada subexpresión en tu expresión original.

(Advertencia, también soy un poco aficionado en estos asuntos, y es posible que haya cometido un error tipográfico o haya hecho trampa inadvertidamente en algún lugar aquí).

Respondida el 19/12/2008 a las 21:33
fuente por usuario

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more