Параметрическость и проективные исключения для зависимых записей

A \times B ≜ \forall α . (A \to B \to α) \to α

$A \times B \triangleq \forall\alpha.\; (A \to B \to \alpha) \to \alpha$

π_{1} : A \times B \to A

$\pi_1 : A \times B \to A$

π_{2} : A \times B \to B

$\pi_2 : A \times B \to B$

Это не так удивительно, хотя естественное чтение типа F - это пара с исключением в стиле let $\mathsf{let}\;(x,y) = p \;\mathsf{in}\; e$ , потому что два вида пары взаимозависимы в интуиционистской логике.

Теперь в теории зависимых типов с нечетким количественным определением вы можете следовать тому же шаблону для кодирования зависимого типа записи $\Sigma x:A.\; B[x]$ as

Σ x : A . B [x] ≜ \forall α . (Π x : A . B [x] \to α) \to α

$\Sigma x:A.\;B[x] \triangleq \forall\alpha.\; (\Pi x:A.\; B[x] \to \alpha) \to \alpha$ Но в этом случае не существует простого способа определения проективных элиминаторов

π_{1} : Σ x : A . B [x] \to A

$\pi_1 : \Sigma x:A.\;B[x] \to A$ и

π_{2} : Π p : (Σ x : A . B [x]) . B [π_{1} p]

$\pi_2 : \Pi p:(\Sigma x:A.\;B[x]).\; B[\pi_1\,p]$ .

Однако, если теория типов является параметрической, вы можете использовать параметричность, чтобы показать, что $\pi_2$ определимо. Кажется, это известно - см., Например, эту разработку Agda Дэна Доэла, в которой он выводит ее без комментариев, - но я не могу найти ссылку на этот факт.

Кто-нибудь знает ссылку на тот факт, что параметричность позволяет определять проективные исключения для зависимых типов?

РЕДАКТИРОВАТЬ: Самая близкая вещь, которую я нашел до сих пор, это статья 2001 года Германа Гойверса, « Индукция» не выводима в теории зависимых типов второго порядка , в которой он доказывает, что вы не можете сделать это без параметризации.

reference-request pl.programming-languages dependent-type parametricity Нил Кришнасвами
источник

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

Виджай Д

Я добавил явную строку вопроса над правкой. Это помогает?

Нил Кришнасвами

Да. Сначала я просто не был уверен, был ли это только справочный запрос или запрос на доказательство. Я спрошу вокруг.

Виджай Д

У меня была дискуссия пару месяцев назад здесь: queuea9.wordpress.com/2012/03/28/why-not-lambda-encode-data, и я считаю, что принцип параметричности -> исключения - это фольклорная / оригинальная работа Дэна. Эти обсуждения близки к другим в отношении параметричности Ж.-П. Бернарди. Возможно, вы захотите взглянуть на разработки стандартной библиотеки Coq вокруг зависимых сумм: coq.inria.fr/stdlib/Coq.Init.Specif.html и, возможно, coq.inria.fr/stdlib/Coq.Logic.EqdepFacts.html#

Коди

@kvb: пока не думаю, что есть положительный ответ. В моем недавнем проекте (с Дереком Дрейером) о параметричности в исчислении конструкций ( mpi-sws.org/~neelk/internalizing-parametricity.pdf ) мы показываем, что параметричность делает правильными добавление аксиом, которые позволяют получить сильные элимы церковного кодирования. Тем не менее, у нас пока нет хорошей истории о том, как усваивать параметричность таким образом, чтобы она хорошо вычислялась (скорее всего, нам нужно интегрировать методы Дж. П. Бернарди в нашу теорию типов). Это не кажется невозможным, но мы пока не знаем как.

Нил Кришнасвами

Я только что поговорил с Дэном Доэлом, и он объяснил, что на самом деле он упоминал Нила Кришнасвами. Он увидел ваш комментарий о n-cafe, что можно сделать сильную индукцию, используя параметричность, поэтому он пошел дальше и сделал это в качестве упражнения, не понимая, что выполнение этого для сигмы, по-видимому, является новым результатом.

Точная цитата: «Моя ссылка была на него. Я думал, он сказал, что это возможно, поэтому я сделал это».

sclv
источник

Параметрическость и проективные исключения для зависимых записей

Ответы: