Что мы получаем, имея «зависимые типы»?

Я думал, что правильно понял зависимую типизацию (DT), но ответ на этот вопрос: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% Теория типа «создать творческий интуиционизм» заставила меня думать иначе.

После прочтения DT и попыток понять, что они из себя представляют, я пытаюсь задаться вопросом, что мы получаем от этого понятия DT? Они кажутся более гибкими и мощными, чем просто типизированное лямбда-исчисление (STLC), хотя я не могу точно понять, «как / почему».

Что мы можем сделать с DT, что нельзя сделать с STLC? Похоже, добавление DT делает теорию более сложной, но в чем выгода?

Из ответа на поставленный выше вопрос:

Зависимые типы были предложены де Брюйном и Говардом, которые хотели расширить соответствие Карри-Говарда от логики высказываний до логики первого порядка.

Кажется, на каком-то уровне это имеет смысл, но я все еще не могу понять общую картину «как / почему»? Может быть, пример, явно показывающий, что это расширение соответствия CH логике FO могло бы помочь понять, в чем заключается проблема с DT? Я не уверен, что понимаю это так же хорошо, как должен.

logic type-theory intuition кандидат наук
источник

Вы гуглили их? Вы слышали о Coq, доказательстве теорем, построенном на зависимых типах? Знаете ли вы, что теорема о 4 цветах доказала использование Coq?

Дейв Кларк

Я сделал на самом деле. Что тяжело для Google, так это то, что является той «мощью» (из-за отсутствия лучшего слова), которую DT дают теории типов, интуитивно говоря?

кандидат наук

Почему? Зависимые типы позволяют печатать больше программ, в то же время сохраняя безопасность типов. Как? Путем параметризации типов с программами.

Мартин Бергер

@MartinBerger - Не могли бы вы рассказать о «большем количестве программ»? Что «больше» я могу сделать или нуждаться с теоретической точки зрения?

кандидат наук

@DaveClarke То, что Coq с его причудливыми типами использовался для создания причудливых вещей, не означает, что эти причудливые вещи требуют этих причудливых типов. Например, Twelf добился больших успехов (например, доказательство правильности SML), и это только второй, а не высший порядок. Я видел несколько довольно больших систем, доказанных только с помощью логики первого порядка.

Жиль "ТАК - перестань быть злым"

Ответы:

Расширяю мой комментарий: Зависимые типы могут набирать больше программ. «Больше» просто означает, что набор программ, типизируемых с зависимыми типами, является правильным надмножеством программ, типизируемых в простом типе калькуляции (STLC). Примером может быть , списки длиной , содержащие элементы типа . Выражение является одновременно программой и частью типа. Вы не можете сделать это в STLC. $\lambda$ $List_{2*3+4}(\alpha)$ $10$ $\alpha$ $2*3+4$

Ключевое правило, которое отличает зависимые от не зависимых типов - это приложение:

\frac{Γ ⊢ M : A \to B Γ ⊢ N : A}{Γ ⊢ M N : B} \frac{Γ ⊢ M : Π x^{A} . B Γ ⊢ N : A}{Γ ⊢ M N : B {N / x}}

$\newcommand{\TYPES}[3]{#1 \vdash #2 : #3} \newcommand{\SUBST}[2]{\{#1/#2\}} \frac{ \TYPES{\Gamma}{\color{red}{M}}{A \rightarrow B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{\color{red}{MN}}{B} } \qquad \frac{ \TYPES{\Gamma}{{\color{red}M}}{\Pi x^A. B} \qquad \TYPES{\Gamma}{\color{red}{N}}{A} }{ \TYPES{\Gamma}{{\color{red}{MN}}}{B\SUBST{{\color{red}N}}{x}} }$

Слева у вас есть STLC, где программы в помещении «перетекают» только в программу заключения. Напротив, в правиле зависимого приложения справа программа из правой предпосылки «перетекает» в тип в заключении . $N$ $^1$

Чтобы иметь возможность параметризовать типы с помощью программ, синтаксис зависимых типов должен быть более богатым, и чтобы гарантировать, что типы правильно сформированы, мы используем вторую «систему типизации», называемую видами, которая ограничивает типы. Эта система сортировки по сути является STLC, но «на один уровень выше».

Есть много объяснений зависимых типов. Несколько примеров.

Зависимые типы на работе , по Бове и Дайбер.
Зависимые типы, Аспиналл и Хофманн.
Зависимое программирование в Агде Нореллом и Чепменом.
Лямбда-исчисление с типами , Барендрегт.

$^1$ ^{С точки зрения цветов: с независимыми типами, черные выражения в заключении построены из черных выражений в помещениях, в то время как красные выражения в заключении построены из красных выражений в помещениях. С зависимыми типами цвета могут быть смешаны, имея черные части заключения, построенные из красных и черных частей помещения.}

Мартин Бергер
источник

Теперь, это имеет большой смысл. Возможно, это было очевидно, но по какой-то причине я не мог это понять. Цените переход от комментария к ответу. К сожалению, вопрос был закрыт для закрытия, но я рад за ответ :)

PhD

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

A r r n

$\mathrm{Arr}\ n$

A r r 0 = n a t

$\mathrm{Arr}\ 0 = \mathrm{nat}$

A r r (n + 1) = n a t \to A r r n

$\mathrm{Arr}\ (n+1) = \mathrm{nat}\rightarrow\mathrm{Arr}\ n$

cody

@ Коди, я не уверен, что ты имеешь в виду. Зависимые типы имеют (или могут быть установлены, чтобы иметь) стирание типов в следующем смысле: для всех печатаемых типов P: iff , где - отношение сокращения времени выполнения , (Это упрощенное описание, где функция стирания отображает программы с аннотацией типа на «одинаковые» программы без аннотации.) Может быть, вы имеете в виду что-то другое?

P ⇓ V

$P\Downarrow V$

e r a s e (P) ⇓ e r a s e (V)

$erase(P)\Downarrow erase(V)$

⇓

$\Downarrow$

Мартин Бергер

@MartinBerger: да, в данном случае я говорю об удалении зависимостей в зависимых типах для получения простых типов. Единственный пример, на который я могу указать прямо сейчас, - это доказательство того, что нормализует, если нормализует (например, в книге Барендрегта ).

F_{ω}

$F_\omega$

C o C

$\mathrm{CoC}$

cody

@ Коди, я думаю, это необычно называть этот тип стирания. Какое имя лучше? Может быть, упрощение типа?

Мартин Бергер

Думайте о объявлениях типа как о не более чем утверждениях. В настоящее время все, что вы можете сказать, это такие вещи, как isInt32 (), isCharPtr () и т. Д. Эти различные утверждения выбираются для проверки во время компиляции. Но эта концепция может быть расширена до таких вещей, как: isCharPtr () && isNotNull (). Обнуляемые указатели - огромная проблема. Указатели не должны быть обнуляемыми в качестве позиции по умолчанию, причем обнуляемые указатели являются типом, который не может быть разыменован, не зная, является ли он нулевым или нет. Подобные проблемы, такие как: isPositiveInteger () или isEvenNaturalNumber ().

обкрадывать
источник