Неразрешимость задачи вывода типов в языке с зависимыми типами

Материал из Викиконспекты
Перейти к: навигация, поиск

Лямбда исчисление с зависимыми типами — расширение просто типизированного лямбда-исчисления, которое позволяет типам зависеть от значений. Например, в языке с таким исчислением функция может возвращать не просто пару чисел, а пару чисел, в которой первое число меньше второго, или если ваша функция принимает число [math]n[/math] и возвращает массив длины [math]n[/math], то это можно будет выразить типом этой функции. Зависимые типы добавляют выразительности типовой системе, что приводит к лучшей проверке корректности программы на этапе компиляции. Однако, как будет показано далее, для этого придётся идти на определённые жертвы: почти всегда придётся явно указывать типы выражений, так как компилятор не сможет справиться с выводом типов для них.

[math]\lambda\Pi[/math]-исчисление

Определение:
Множество термов (англ. term) рекурсивно определяется следующей грамматикой:

[math]\displaystyle T ::= \mathrm{Type} \mid \mathrm{Kind} \mid x \mid \left(T\ T\right) \mid \lambda x : T . T \mid \Pi x : T . T[/math].

  • Термы [math]\mathrm{Type}[/math] и [math]\mathrm{Kind}[/math] называются сортами (англ. sorts),
  • [math]x[/math]переменными (англ. variables),
  • [math](t\ t')[/math]применениями (англ. applications),
  • [math]\lambda x : t . t'[/math]абстракциями (англ. abstractions),
  • [math]\Pi x : t . t'[/math]произведениями (англ. products).
Обозначение [math]t \rightarrow t'[/math] используется вместо [math]\Pi x : t . t'[/math], если [math]x[/math] не входит свободно в [math]t'[/math].


Пусть есть термы [math]t[/math] и [math]t'[/math] и переменная [math]x[/math]. Записью [math]t\left[x \leftarrow t'\right][/math] обозначается терм, полученный заменой [math]t'[/math] на [math]t[/math] в [math]x[/math]. Запись [math]t =_\beta t'[/math] означает, что термы [math]t[/math] и [math]t'[/math] [math]\beta[/math]-эквивалентны.

Определение:
Контекст (англ. context) это список пар [math]x : T[/math], где [math]x[/math] — переменная, [math]T[/math] — терм.


Определение:
Правила вывода для нашего исчисления:

[math] \displaystyle \frac{}{\left[ \right] \in \mathrm{WF}} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash T : s}{\Gamma\left[x : T\right] \in \mathrm{WF}} \text{,} \vspace{3mm} \\ \frac{\Gamma \in \mathrm{WF}}{\Gamma \vdash \mathrm{Type} : \mathrm{Kind}} \text{,} \vspace{3mm} \\ \frac{\Gamma \in \mathrm{WF} \qquad x : T \in \Gamma}{\Gamma \vdash x : T} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash T : \mathrm{Type} \qquad \Gamma\left[x : T\right] \vdash T' : s}{\Gamma \vdash \Pi x : T . T' : s} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash \Pi x : T . T' : s \qquad \Gamma\left[x : T\right] \vdash t : T'}{\Gamma \vdash \lambda x : T . t : \Pi x : T . T'} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash t : \Pi x : T . T' \qquad \Gamma \vdash t' : T}{\Gamma \vdash \left(t\ t'\right) : T'\left[x \leftarrow t'\right]} \text{,} \vspace{3mm} \\ \frac{\Gamma \vdash T : s \qquad \Gamma \vdash T' : s \qquad \Gamma \vdash t : T \qquad T =_\beta T'}{\Gamma \vdash t : T'} \text{;} [/math]

где [math]s ::= \mathrm{Type} \mid \mathrm{Kind}[/math], а [math]\mathrm{WF}[/math] — множество корректных контекстов.

Терм [math]t[/math] типизируется (англ. well-typed) в контексте [math]\Gamma[/math], если существует такой терм [math]T[/math], что [math]\Gamma \vdash t : T[/math].


Отношение редуцируемости на типизируемых термах сильно нормализуемо и обладает ромбовидным свойством. Каждый типизируемый терм имеет единственную нормальную форму, два терма эквивалентны, если у них одинаковая нормальная форма.

Типизируемый в контексте [math]\Gamma[/math] терм [math]t[/math] имеет единственный тип с точностью до эквивалентности.

Определение:
Нормальный терм [math]t[/math], типизируемый в контекте [math]\Gamma[/math], имеет либо вид

[math]\displaystyle t = \lambda x_1 : T_1 \ldots \lambda x_n : T_n . \left(x\ c_1\ \ldots\ c_n\right)[/math],

где [math]x[/math] это переменная или сорт, либо вид

[math]\displaystyle t = \lambda x_1 : T_1 \ldots \lambda x_n : T_n . \Pi x : P . Q\text{.}[/math]

Согласимся первым символом (англ. head symbol) [math]t[/math] называть [math]x[/math] в первом случае, и [math]\Pi[/math] во втором. Первыми переменными (англ. top variables) [math]t[/math] будем называть переменные [math]x_1, \ldots, x_n[/math].


Задача вывода типов в [math]\lambda\Pi[/math]-исчислении

Определение:
Терм [math]t[/math] типа [math]T[/math] в контексте [math]G[/math] называется объектом (англ. object) в [math]\Gamma[/math], если [math]\Gamma \vdash T : \mathrm{Type}[/math].


Утверждение:
Если терм [math]t[/math] является объёктом в контексте [math]\Gamma[/math], то он является либо переменной, либо применением, либо абстракцией. Если он является применением [math]t=(u\ v)[/math], тогда оба терма [math]u[/math] и [math]v[/math] являются объектами в [math]\Gamma[/math], если он является абстракцией [math]t=\lambda x : U . u[/math], то тогда терм [math]u[/math] является объектом в контексте [math]\Gamma\left[x : U\right][/math].


Определение:
Множество чистых термов (англ. pure terms) определяется грамматикой [math]T ::= x \mid \left(T\ T\right) \mid \lambda x . T[/math].


Определение:
Пусть [math]t[/math] — объект в контексте [math]\Gamma[/math]. Содержимое (англ. content) [math]t[/math] ([math]\left|t\right|[/math]) — это рекурсивно определённый чистый терм:
  • [math]\left|x\right| = x[/math];
  • [math]\left|\left(t\ t'\right)\right| = \left(\left|t\right|\left|t'\right|\right) [/math];
  • [math]\left|\lambda x : U . t\right| = \lambda x . \left|t\right|[/math].


Определение:
Чистый терм [math]t[/math] называется типизируемым (англ. typable) в контексте [math]\Gamma[/math], если существует терм [math]t'[/math], типизируемый в неком [math]\Gamma\Delta[/math], являющимся расширением [math]\Gamma[/math], что [math]t'[/math] является объектом в [math]\Gamma\Delta[/math] и [math]t=\left|t'\right|[/math].


Типизация чистого терма в контексте [math]\Gamma[/math] это присвоение типов связанным переменным и некоторым свободным переменным, типов которых нет в [math]\Gamma[/math]. Если же контекст [math]\Gamma[/math] пустой, то типизация терма в нём будет являться присваиванием типов и связанным и свободным переменным.

Утверждение:
Задача вывода типов в пустом контексте разрешима в [math]\lambda\Pi[/math]-исчислении.
[math]\triangleright[/math]
Типизируемые в пустом контексте чистые термы [math]\lambda\Pi[/math] исчисления совпадают с типизируемыми выражениями просто типизированного [math]\lambda[/math]-исчисления, а задача вывода типов в просто типизированном [math]\lambda[/math]-исчислении разрешима.
[math]\triangleleft[/math]

Неразрешимость задачи вывода типов в [math]\lambda\Pi[/math]-исчислении

Рассмотрим контекст [math]\Gamma=\left[T : \mathrm{Type}; a : T \rightarrow T; b : T \rightarrow T; c : T; d : T; P : T \rightarrow \mathrm{Type}; F : \Pi x : T.\left(\left(P\ x\right) \rightarrow T\right)\right][/math].


Определение:
Пусть [math]\varphi[/math] — слово двухсимвольного алфавита [math]\left\{A, B\right\}[/math]. Определим [math]\hat{\varphi}[/math] и [math]\tilde{\varphi}[/math] следующим образом:
  • [math]\hat{\varepsilon} = \lambda y : T . y[/math];
  • [math]\hat{A\ \varphi} = \lambda y : T.\left(a\ \left(\hat{\varphi}\ y\right)\right)[/math];
  • [math]\hat{B\ \varphi} = \lambda y : T.\left(b\ \left(\hat{\varphi}\ y\right)\right)[/math];
  • [math]\tilde{\varphi}=\left|\hat{\varphi}\right|[/math].


Утверждение:
Рассмотрим проблему соответствий Поста для списков слов над двухсимвольным алфавитом [math]\left(\varphi_1, \ldots, \varphi_n\right)[/math] и [math]\left(\psi_1, \ldots, \psi_n\right)[/math]. Непустая последовательность [math]\left(i_1,\ldots,i_p\right)[/math] является её решением тогда и только тогда, когда [math](\hat{\varphi_{i_1}}\ (\ldots (\hat{\varphi_{i_p}}\ c)\ldots)) =_\beta (\hat{\psi_{i_1}}\ (\ldots (\hat{\psi_{i_p}}\ c)\ldots))[/math].
Утверждение:
Если [math]g[/math] это такой терм, что терм [math](g\ a \ldots a)[/math] ([math]a[/math] повторяется [math]n[/math] раз) типизируемый, и он является объектом в неком [math]\Gamma\Delta[/math], то тогда терм [math]g[/math] типизируется в контексте [math]\Gamma\Delta[/math], и его тип эквивалентен терму [math]\Pi x_1 : T \rightarrow T \ldots \Pi x_n : T \rightarrow T . (\beta\ x_1 \ldots x_n)[/math] для какого-то терма [math]\beta[/math] типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow \mathrm{Type}[/math] в контексте [math]\Gamma\Delta[/math].
[math]\triangleright[/math]
Индукция по [math]n[/math].
[math]\triangleleft[/math]
Утверждение:
Пусть [math]t,u_1,\ldots,u_n,v[/math] — такие нормальные термы, что [math](t\ u_1\ldots u_n)[/math] — типизируемый терм, и его нормальная форма это [math]v[/math]. Тогда первый символ [math]t[/math] это либо первый символ [math]v[/math], либо первая переменная [math]t[/math].
[math]\triangleright[/math]
Пусть [math]x[/math] — первый символ [math]t[/math]. Если [math]x[/math] не является первой переменной [math]t[/math], то первый символ нормальной формы [math](t\ u_1 \ldots u_n)[/math] это тоже [math]x[/math], значит, [math]x[/math] это первый символ [math]v[/math].
[math]\triangleleft[/math]
Утверждение:
Пусть [math]t[/math] — такой нормальный терм типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow T[/math] в контексте [math]\Gamma[/math], что нормальная форма [math](t\ \lambda y : T.y \ldots \lambda y : T.y)[/math] равна [math]c[/math]. Тогда терм [math]t[/math] является термом вида [math]t=\lambda x_1 : T \rightarrow T \ldots \lambda x_n : T \rightarrow T . (x_{i_1}\ (\ldots (x_{i_p}\ c)\ldots))[/math] для некой последовательности [math]i_1,\ldots,i_p[/math].
[math]\triangleright[/math]
Индукция по числу переменных в [math]t[/math].
[math]\triangleleft[/math]
Теорема:
Задача проверки типизируемости чистого терма в заданном контексте неразрешима.
Доказательство:
[math]\triangleright[/math]

Рассмотрим проблему соответствий Поста для списков слов над двухсимвольным алфавитом [math]\left(\varphi_1, \ldots, \varphi_n\right)[/math] и [math]\left(\psi_1, \ldots, \psi_n\right)[/math]. Построим такой чистый терм [math]t[/math], что [math]t[/math] типизируем в [math]\Gamma[/math] тогда и только тогда, когда проблема соответствий поста имеет решение.

[math] \begin{aligned} t = \lambda f . \lambda g . \lambda h . (f\ &(g\ a \ldots a)\\ &(h\ (g\ \tilde{\varphi_1} \ldots \tilde{\varphi_n}))\\ &(h\ (g\ \tilde{\psi_1} \ldots \tilde{\psi_n}))\\ &(F\ c\ (g\ \lambda y.y \ldots \lambda y.y))\\ &(F\ d\ (g\ \lambda y.d \ldots \lambda y.d)))\text{.} \end{aligned} [/math]

Предположим, что этот терм типизируем, и обозначим тип [math]g[/math] как [math]\alpha[/math]. Терм [math](g\ a \ldots a)[/math] типизируется и является объектом в [math]\Gamma\Delta[/math], значит,

[math]\alpha =_\beta \Pi x_1 : T \rightarrow T \ldots \Pi x_n : T \rightarrow T . (\beta\ x_1 \ldots x_n)[/math],

где [math]\beta[/math] это терм типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow \mathrm{Type}[/math] в [math]\Gamma\Delta[/math].

Тогда все переменные [math]y[/math], связанные в термах [math]\hat{\varphi_i}[/math], [math]\tilde{\psi_i}[/math], [math]\lambda y.y[/math] и [math]\lambda y.d[/math], имеют тип [math]T[/math]. Терм [math](g \ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n})[/math] имеет тип [math](\beta\ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n})[/math], тогда из типизируемости терма [math](h\ (g \ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n}))[/math] мы получаем, что тип переменной [math]h[/math] имеет вид [math]\Pi x : \gamma : \gamma'[/math], и

[math]y =_\beta (\beta\ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n})[/math].

Точно так же, из типизируемости терма [math](h\ (g \ \hat{\psi_1} \ \ldots\ \hat{\psi_n}))[/math] получаем, что

[math]y =_\beta (\beta\ \hat{\psi_1} \ \ldots\ \hat{\psi_n})[/math],

значит,

[math](\beta\ \hat{\varphi_1} \ \ldots\ \hat{\varphi_n}) =_\beta (\beta\ \hat{\psi_1} \ \ldots\ \hat{\psi_n})[/math].

Из типизируемости терма [math](F\ c\ (g\ \lambda y : T.y\ldots \lambda y : T . y))[/math] получаем

[math](\beta\ \lambda y:T.y \ldots \lambda y:T.y) =_\beta (P\ c)[/math].

Наконец, из типизируемости терма [math](F\ d\ (g\ \lambda y : T.d\ldots \lambda y : T . d))[/math] получаем

[math](\beta\ \lambda y:T.d \ldots \lambda y:T.d) =_\beta (P\ d)[/math].

Поскольку терм [math]\beta[/math] имеет тип [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow \mathrm{Type}[/math], первый символ нормальной формы терма [math]\beta[/math] не может быть первой переменной [math]\beta[/math], значит, это переменная [math]P[/math], и мы получаем, что

[math]\beta =_\beta \lambda x_1 : T \rightarrow T \ldots \lambda x_n : T \rightarrow T.(P\ (\delta\ x_1 \ldots x_n))[/math],

где [math]\delta[/math] — некий терм типа [math](T \rightarrow T) \rightarrow \ldots \rightarrow (T \rightarrow T) \rightarrow T[/math]. Получаем, что

[math] (\delta\ \hat{\varphi_1} \ldots \hat{\varphi_n}) =_\beta (\delta\ \hat{\psi_1} \ldots \hat{\psi_n})\text{,} \\ (\delta\ \lambda y:T.y \ldots \lambda y:T.y) =_\beta c \text{,}\\ (\delta\ \lambda y:T.d \ldots \lambda y:T.d) =_\beta d \text{.} [/math]

Вторая эквивалентность показывает, что нормальная форма [math]\delta[/math] имеет вид

[math]\lambda x_1:T \rightarrow T \ldots \lambda x_n : T \rightarrow T . (x_{i_1}\ (\ldots(x_{i_p}\ c)\ldots))[/math]

для некоторой последовательности [math]i_1,\ldots,i_p[/math]. Третья эквивалентность показывает, что [math]p\gt 0[/math], и первая — что

[math](\hat{\varphi_{i_1}}\ (\ldots(\hat{\varphi_{i_p}\ c})\ldots)) =_\beta (\hat{\psi_{i_1}}\ (\ldots(\hat{\psi_{i_p}\ c})\ldots))[/math],

то есть последовательность [math]i_1,\ldots,i_p[/math] является решением проблемы Поста.

И наоборот, если предположить, что проблема Поста имеет решение [math]i_1,\ldots,i_p[/math], то можно задать типы переменным [math]f[/math], [math]g[/math] и [math]h[/math]:

[math] f : (P\ (a\ (\ldots(a\ c)\ldots))) \rightarrow T \rightarrow T \rightarrow T \rightarrow T \rightarrow T \text{,}\\ g : \Pi x_1 : T \rightarrow T \ldots \Pi x_n : T \rightarrow T.(P\ (x_{i_1}\ (\ldots(x_{i_p}\ c)\ldots))) \text{,}\\ h : (P\ (\hat{\varphi_{i_1}}\ (\ldots(\hat{\varphi_{i_p}}\ c)\ldots))) \rightarrow T \text{;} [/math]

и тип [math]T[/math] всем остальным переменным терма [math]t[/math], и получить такой типизируемый в [math]\Gamma[/math] терм [math]t'[/math], который является объектом и [math]t = \left|t'\right|[/math].
[math]\triangleleft[/math]

См. также

Источники информации