통일 문제에 대한 유도

Question

유형의 추론이 어떻게 문제가되는지 아이디어가 있습니까?

E > hd (cons 1 nil) : α0

타이핑 환경으로

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

통일 문제에서 전송 될 수 있습니까?

모든 도움이 정말 감사하겠습니다!

Answer 1

먼저, 표현식의 변수 중 어느 것도 타이핑 환경에서 변수와 충돌하지 않도록 유형 변수 이름을 바꿉니다. (예에서는 표현식 참조 {A0} 이후 이미 수행됩니다. {A1, A2, A3} 타이핑 환경 참조.

둘째, 새로운 유형 변수를 사용하여 표현식 내의 모든 서브 표현에 대한 유형 변수를 만들어 다음과 같은 것을 생성합니다.

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

셋째, 유지 해야하는 유형 변수 중 일련의 방정식을 생성하십시오. 하단에서 상단에서 또는 다른 방식 으로이 작업을 수행 할 수 있습니다. 보다 헤렌, 바스 티아 인. 최고 품질 유형 오류 메시지. 2005. 왜 어떤 방식 으로든 선택하고 싶은 이유에 대한 광범위한 세부 사항은. 이것은 다음과 같은 것입니다.

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

유형 환경에서 동일한 함수를 두 번 사용하는 경우 통일을 위해 더 많은 새로운 유형 변수 (위의 두 번째 단계)가 필요하므로 실수로 모든 통화를 동일한 유형을 사용하지 않도록하십시오. . 이 부분을 더 명확하게 설명하는 방법을 잘 모르겠습니다. 죄송합니다. 여기서 우리는 HD와 단점이 각각 한 번만 사용되므로 쉬운 경우에 있습니다.

넷째, 이러한 방정식을 통합하여 다음과 같은 것 (실수하지 않은 경우)을 초래합니다.

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

기뻐하십시오. 이제 원래 표현에서 모든 하위 표현의 유형을 알 수 있습니다.

(공정한 경고, 나는이 문제들에 대해 다소 아마추어가되어 있으며, 나는 인쇄상의 오류를 일으키거나 부주의하게 여기 어딘가에 부정 행위를했을 것입니다.)