Тип вывода для объединения проблемы

голоса
2

Кто-нибудь представление о том, как проблема логического вывода типа

E > hd (cons 1 nil) : α0

с окружающей средой, набрав

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

могут быть переданы в задаче объединения?

Любая помощь будет очень признателен!

Задан 09/12/2008 в 14:58
источник пользователем
На других языках...                            


1 ответов

голоса
3

Во-первых, переименовать переменные типа так, что ни одна из переменных в выражении не сталкиваются с переменными в среде печати. (В вашем примере, это уже сделано, так как ссылки выражения {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

В- третьих, создать набор уравнений между переменными типа , которые должны содержать. Вы можете сделать это снизу вверх, сверху вниз, или другими способами. См Heeren, Бастиан. Лучшего качество Сообщение об ошибках Типа. 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

Радуйтесь, теперь вы знаете, тип каждого подвыражения в своем первоначальном выражении.

(Справедливое предупреждение, я несколько любительского себя в этих вопросах, и я, возможно, хорошо сделал типографскую ошибку или неумышленно изменял где-то здесь.)

Ответил 19/12/2008 в 21:33
источник пользователем

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