Inferência de tipos de problema unificação

votos
2

Alguém tem uma idéia de como o problema de inferência tipo

E > hd (cons 1 nil) : α0

com o ambiente de digitação

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

pode ser transferido em um problema de unificação?

Qualquer ajuda seria realmente apreciada!

Publicado 09/12/2008 em 14:58
fonte usuário
Em outras línguas...                            


1 respostas

votos
3

Em primeiro lugar, mudar o nome de variáveis ​​tipo de modo que nenhuma das variáveis ​​em sua expressão colidir com variáveis ​​no ambiente de digitação. (No seu exemplo, isso já é feito desde as referências de expressão {a0}, e as referências ambiente digitação {a1, a2, a3}.

Em segundo lugar, a utilização de novas variáveis ​​do tipo, faça uma variável do tipo para cada subexpressão dentro de sua expressão, produzindo algo como:

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

Em terceiro lugar, gerar um conjunto de equações entre as variáveis do tipo que deve conter. Você pode fazer isso a partir de baixo para cima, de cima para baixo, ou de outras formas. Veja Heeren, Bastiaan. Mensagens de erro tipo de qualidade superior. 2005. para maiores detalhes sobre por que você pode querer escolher uma forma ou de outra. Isto irá resultar em 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

Note cuidadosamente que se a mesma função foi utilizada a partir do tipo de ambiente duas vezes, seria preciso mais novas variáveis ​​do tipo (na segunda etapa, acima) para unificar com, de modo que nós não acidentalmente fazer todas as chamadas para contras usar o mesmo tipo . Eu não sei como explicar esta parte de forma mais clara, desculpe. Aqui estamos nós, no caso fácil, já que hd e contras são cada utilizado apenas uma vez.

Em quarto lugar, unificar essas equações, resultando em (se eu não tiver cometido um erro) algo como:

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

Alegrai-vos, agora você sabe o tipo de cada sub-expressão na sua expressão original.

(Fair aviso, eu sou um pouco de um amador mim mesmo nesses assuntos, e eu pode muito bem ter feito um erro de digitação ou inadvertidamente enganado em algum lugar aqui.)

Respondeu 19/12/2008 em 21:33
fonte usuário

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