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

16

π 1 : A × B A π 2 : A × B B

A×Bα.(ABα)α
π1:A×BAπ2:A×BB

Это не так удивительно, хотя естественное чтение типа F - это пара с исключением в стиле let let(x,y)=pine , потому что два вида пары взаимозависимы в интуиционистской логике.

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

Σx:A.B[x]α.(Πx:A.B[x]α)α
Но в этом случае не существует простого способа определения проективных элиминаторов π1:Σx:A.B[x]A и π2:Πp:(Σx:A.B[x]).B[π1p] .

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

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

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

Нил Кришнасвами
источник
Я не могу сказать из этого поста, в чем вопрос. (Я ничего не знаю об этом районе и не знаю в любом случае, но я бы хотел сформулировать вопрос)
Виджай Д
2
Я добавил явную строку вопроса над правкой. Это помогает?
Нил Кришнасвами
Да. Сначала я просто не был уверен, был ли это только справочный запрос или запрос на доказательство. Я спрошу вокруг.
Виджай Д
У меня была дискуссия пару месяцев назад здесь: 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#
Коди
1
@kvb: пока не думаю, что есть положительный ответ. В моем недавнем проекте (с Дереком Дрейером) о параметричности в исчислении конструкций ( mpi-sws.org/~neelk/internalizing-parametricity.pdf ) мы показываем, что параметричность делает правильными добавление аксиом, которые позволяют получить сильные элимы церковного кодирования. Тем не менее, у нас пока нет хорошей истории о том, как усваивать параметричность таким образом, чтобы она хорошо вычислялась (скорее всего, нам нужно интегрировать методы Дж. П. Бернарди в нашу теорию типов). Это не кажется невозможным, но мы пока не знаем как.
Нил Кришнасвами

Ответы:

6

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

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

sclv
источник